题解 P1855 【榨取kkksc03】

孤独的死男孩 · 2019-10-16 17:31:06 · 题解

- 看到这题题目感到很奇葩，读了之后感觉更奇葩这分明是kkksc003自己压榨自己啊-

• 这题实际是基础二维01背包所以难度设定有问题
• 废话不多说，以下是思路：
• 这题转移方程是f[j][k]=max(f[j][k],f[j-wish_money[i]][k-wish_time[i]]+1)
• 解释一下就是选取此物与不选取此物之间谁比较好j枚举kkksc003的金钱，k枚举时间
• 之后用转移方程枚举从f[0][0]到f[m][t]，输出f[m][t],以下是代码：

  #include<iostream>
  using namespace std;
  int wish_m[105]={0},wish_t[105]={0},f[205][205];
  int main(){
  int n,m,t;
  cin>>n>>m>>t;
  for(int i=0;i<n;i++){
      cin>>wish_m[i]>>wish_t[i];
  }
  for(int i=0;i<n;i++){
      for(int j=m;j>=wish_m[i];j--){
          for(int k=t;k>=wish_t[i];k--){
              f[j][k]=max(f[j-wish_m[i]][k-wish_t[i]]+1,f[j][k]);
          }
      }
  }
  cout<<f[m][t];
  return 0;
  }

  话说真心觉得数据加强一下，以我这个小菜鸟都能10分钟1A