mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
264 字
1 分钟
动态规划-dp复健1
2026-11-07

题目说要求的状态与最终的目标可能相同可能不同,但是大概分为几种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/
作者
Hydroiody
发布于
2026-11-07
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

目录