8615 快乐-白红宇

8615 快乐

阅读量：619 次

发布时间：2019-03-13

本文共 1646 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要帮助Lian计算他能获得的最大快乐指数，同时确保他最后至少还有1点精力。这个问题可以通过动态规划来解决，类似于背包问题。

方法思路

问题分析：Lian有n道题，每道题可以增加一定的快乐指数并消耗一定的精力。我们需要选择题目使得快乐指数最大化，同时确保最后剩余的精力至少为1。

动态规划定义：定义dp[i][j]为处理了前i道题，消耗了j点精力时的最大快乐指数。

状态转移：对于每道题i，处理j从2000到0，更新dp表。选择做或不做当前题，取最大值。

初始化：初始状态为dp[0][j] = 1，表示不做任何题时的快乐指数为1。

结果计算：遍历所有可能的j值，找到处理完所有题后剩余精力至少1时的最大快乐指数。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    // 读取输入    int n;    cin >> n;    vector
      
        gethappy(n + 1);  // gethappy[1..n]    vector
       
         losspow(n + 1);  // losspow[1..n]    for (int i = 1; i <= n; ++i) {        cin >> gethappy[i];    }    for (int i = 1; i <= n; ++i) {        cin >> losspow[i];    }    // 初始化动态规划数组    vector
        
         
          > dp(n + 1, vector
          
           (2001, 0)); for (int j = 0; j <= 2000; ++j) { dp[0][j] = 1; // 初始状态：不做任何题时，快乐值为1 } // 处理每一道题 for (int i = 1; i <= n; ++i) { for (int j = 2000; j >= 0; --j) { if (j >= losspow[i]) { // 可以做这道题 int option1 = dp[i-1][j]; // 不做这道题 int option2 = dp[i-1][j - losspow[i]] + gethappy[i]; // 做这道题 dp[i][j] = max(option1, option2); } else { // 不能做这道题 dp[i][j] = dp[i-1][j]; } } } // 查找最大快乐值，剩余精力必须大于0 int max_happiness = 0; for (int j = 0; j < 2000; ++j) { // 剩余精力必须至少1 if (dp[n][j] > max_happiness) { max_happiness = dp[n][j]; } } cout << max_happiness << endl; return 0;}

代码解释

读取输入：读取题目数量n，以及每道题的快乐指数和精力消耗。

初始化动态规划数组：dp数组初始化为2001个元素，表示从0到2000的精力状态。初始状态dp[0][j] = 1，表示不做任何题时的快乐指数为1。

处理每道题：遍历每道题，对每个可能的精力状态j进行处理，更新dp数组，选择做或不做当前题，取最大值。

计算最大快乐指数：遍历所有可能的精力状态，找到处理完所有题后剩余精力至少1时的最大快乐指数。

通过这种方法，我们可以有效地解决问题，确保Lian获得最大快乐指数。

转载地址：http://olraz.baihongyu.com/

你可能感兴趣的文章

PAT甲级——1009 Product of Polynomials (25分)（最后一个测试点段错误）