264 字
1 分钟
动态规划-dp复健1
题目说要求的状态与最终的目标可能相同可能不同,但是大概分为几种dp的目标:
-
可达性 DP:能不能达到某个状态?
-
最优化 DP:达到某个状态的最大价值或最小代价是多少?
-
计数 DP:达到某个状态有多少种方案? 可能为1种,也可能有多种混合
https://codeforces.com/problemset/problem/189/A
int n,a,b,c;void solve(){ cin>>n>>a>>b>>c; vector<int> arr={0,a,b,c}; vector<vector<int>> dp(4,vector<int>(n+1,-1)); for(int i=1;i<=3;i++){ dp[i][0]=0; } for(int i=1;i<=3;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]; if(j>=arr[i]&&dp[i][j-arr[i]]!=-1){ dp[i][j]=max(dp[i][j],dp[i][j-arr[i]]+1); } } } cout<<dp[3][n];}一开始没看出来是dp,结合数据量和复杂程度,一根大于a+b+c的绳子有多种组合,并且要注意 可达状态和不可达状态,如果存在非abc的情况就是不可达状态,有点像迷宫问题中重复走过的格子要标注为不可达。表面上问的是有多少种,好像是计数,但是有最大值的需求,属于最优化dp问题,同时也要关注状态的可达与不可达,当然解法是背包dp
D - Money in Hand
int n,x;
void solve(){ cin>>n>>x; vector<int> a(n),b(n); int sum=0; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; sum+=b[i]; } vector<vector<int>> dp(sum+1,vector<int>(x+1,0)); for(int i=0,cur=0;i<n;i++){ for(int j=1;j<=b[i];j++){ for(int k=1;k<=x;k++){ if(k>=a[i]){ dp[cur+j][k]=max( dp[j+cur-1][k], dp[j+cur-1][k-a[i]]+a[i] ); } else{ dp[cur+j][k]=dp[j+cur-1][k]; } } } cur+=b[i]; } cout<<(dp[sum][x]==x?"Yes":"No");} 分享
如果这篇文章对你有帮助,欢迎分享给更多人!
动态规划-dp复健1
https://blog.hydrodyio.xyz/posts/动态规划-dp复健1/ 部分信息可能已经过时
相关文章 智能推荐








