首页 > 代码库 > [HDU 2546]饭卡 (动态规划)

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

2024-07-27 12:08:24   222人阅读

题目链接：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时

 

代码：

 1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 typedef long long LL; 6 typedef pair<int,int> PII; 7 #define PB push_back 8 #define SZ size() 9 #define X first10 #define Y second11 12 const int MAX_N = 1100;13 int N,M,v[MAX_N],dp[MAX_N][MAX_N];14 15 int main(){16     while(~scanf("%d",&N)&&N){17         for(int i=1;i<=N;i++) scanf("%d",&v[i]);18         scanf("%d",&M);19         sort(v+1,v+N+1);20         for(int i=0;i<=M;i++) dp[N+1][i] = i;21         for(int i=N;i>=1;i--){22             for(int j=M;j>=0;j--){23                 if( j<5 ) dp[i][j] = j;24                 else if( j-v[i]>=5 ) dp[i][j] = min(dp[i+1][j],dp[i+1][j-v[i]]);25                 else dp[i][j] = min(dp[i+1][j],j-v[i]);26             }27         }28         printf("%d\n",dp[1][M]);29     }30     return 0;31 }

 

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


联系
我们