RQNOJ 329 刘翔！加油！：01背包

题目链接：https://www.rqnoj.cn/problem/329

题意：

　　刘翔有n封信，每封信都有自己的欣赏价值value[i]、消耗时间time[i]、消耗体力h[i]、和得到的鼓舞w[i]。

　　观看信件必须按照价值递增（大于）的顺序观看，不一定需要全看。

　　可是，刘翔在伤病中，时间和体力分别为t,m，同时看完之后体力不能为0。

　　问你受到的鼓舞最大为多少。

题解：

　　这道题里value[i]真的没有用。。。

　　表示状态：

　　　　dp[i][j][k] = max encouraging

　　　　i：考虑到第i封信

　　　　j：花费的时间

　　　　k：花费的体力

　　找出答案：

　　　　ans = max dp[i][j][k] (0<=j<=t, 0<=k<m)

　　如何转移：

　　　　dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-c[i]][k-h[i]] + w[i])　（01背包）

　　边界条件：

　　　　set dp = 0

AC Code:

 // state expression:

 // dp[i][j][k] = max encouraging

 // i: ith letter was considered

 // j: time cost

 // k: hp cost

 //

 // find the answer:

 // max dp[i][j][k] (0<=j<=t, 0<=k<m)

 //

 // transferring:

 // dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-c[i]][k-h[i]] + w[i])

 //

 // boundary:

 // set dp = 0

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 105

 #define MAX_T 105

 #define MAX_H 105

 using namespace std;

 int n,m,t;

 int ans;

 int w[MAX_N];

 int c[MAX_N];

 int h[MAX_N];

 int dp[MAX_N][MAX_T][MAX_H];

 void read()

 {

     cin>>n>>m>>t;

     int v;

     for(int i=;i<=n;i++)

     {

         cin>>v>>c[i]>>h[i]>>w[i];

     }

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

     ans=;

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=t;j++)

         {

             for(int k=;k<m;k++)

             {

                 dp[i][j][k]=max(dp[i][j][k],dp[i-][j][k]);

                 if(j-c[i]>= && k-h[i]>=)

                 {

                     dp[i][j][k]=max(dp[i][j][k],dp[i-][j-c[i]][k-h[i]]+w[i]);

                 }

                 ans=max(ans,dp[i][j][k]);

             }

         }

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 329 刘翔！加油！：01背包

最新文章

热门文章