dp 二维乃至多维背包

洛谷P1855 榨取kkksc03

分析:套路是很明显的01背包,但是这时受约束的变量有两个了,这种情况下就该用多维背包了

分析方法一样的,用dp[i][j][k]表示从前i个愿望中挑选总时间和总金钱不超过j,k时的最大愿望数。

则状态转移方程应该为:dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-tme[i]][k-mny[i]]+1).

因为多维数组,虽然这题数据量小,但是能用滚动数组就尽量用吧。

上代码:

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-);
int tme[],mny[];
int dp[][];
int main(){
int n,m,t;scanf("%d%d%d",&n,&m,&t);
for(int i=;i<n;i++)scanf("%d%d",&tme[i],&mny[i]);
for(int i=;i<n;i++){
for(int j=t;j>=tme[i];j--){
for(int k=m;k>=mny[i];k--){
dp[j][k]=max(dp[j][k],dp[j-tme[i]][k-mny[i]]+);
}
}
}
cout<<dp[t][m]<<endl;
return ;
}
上一篇:解决hive交互模式退格键乱码


下一篇:dp之二维背包poj1837(天平问题 推荐)