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 ;

 }

巴特西

dp 二维乃至多维背包

最新文章

热门文章