[HDU 2546]饭卡 (动态规划)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546

题意：见题目

刚开始怎么写都写不对，后来吃饭的时候想了想记忆化搜索的办法

就是说设dp(now,rev)为我现在要选择now这个物品，此时我手里剩下了rev这么多的钱。那么如果我手里剩下的钱不少于5块钱的话就可以向下转移

这时候dp(now,rev) = min( dp(now+1,rev) , dp(now+1,rev-v[now] ) )

如果说我手里这时候剩下了的钱数不超过5元，那么我什么也买不了，于是就直接返回rev

注意选物品的时候要价值低的物品先选，这样可以保证我选了价值低的物品后还有可能选择价值高的物品。

反之如果先选了价值高的物品，那么有可能选完了价值高的物品后就选不了价值低的物品了。

改写成递推的话就有：

dp[i][j] = j; 当 j < 5 时，此时我什么也买不了

dp[i][j] = min( dp[i+1][j], dp[i+1][j-v[i]] ); 当j-v[i]>=5时

dp[i][j] = j - v[i] ; 当 j - v[i] < 5时

代码：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> PII;

 #define PB push_back

 #define SZ size()

 #define X first

 #define Y second

 const int MAX_N = ;

 int N,M,v[MAX_N],dp[MAX_N][MAX_N];

 int main(){

     while(~scanf("%d",&N)&&N){

         for(int i=;i<=N;i++) scanf("%d",&v[i]);

         scanf("%d",&M);

         sort(v+,v+N+);

         for(int i=;i<=M;i++) dp[N+][i] = i;

         for(int i=N;i>=;i--){

             for(int j=M;j>=;j--){

                 if( j< ) dp[i][j] = j;

                 else if( j-v[i]>= ) dp[i][j] = min(dp[i+][j],dp[i+][j-v[i]]);

                 else dp[i][j] = min(dp[i+][j],j-v[i]);

             }

         }

         printf("%d\n",dp[][M]);

     }

     return ;

 }

巴特西

[HDU 2546]饭卡 (动态规划)

最新文章

热门文章