多重背包求助!请不要无意义回复!
  • 板块P1717 钓鱼
  • 楼主qpdk777
  • 当前回复15
  • 已保存回复15
  • 发布时间2020/6/3 16:53
  • 上次更新2023/11/7 01:14:18
查看原帖
多重背包求助!请不要无意义回复!
261932
qpdk777楼主2020/6/3 16:53
#include<iostream>
#include<cstdio>
using namespace std;

int ans;
int n,h,a[110],b[110],t[110],mt[110];
int dp[110][300],num[110][300];

int main(){
    ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    cin>>n>>h;
    h *= 12;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    for(int i = 1; i <= n; ++i)
        cin>>b[i];
    for(int i = 1; i <= n-1; ++i)
        cin>>t[i];
    mt[0] = h;
    for(int i = 1; i <= n; ++i){
        mt[i] = mt[i-1]-t[i-1];
        for(int j = 1; j<=mt[i]; ++j){
            num[i][j] = a[i]+num[i][j-1];//预处理在第i个池塘钓鱼j分钟的收获
            a[i] -= b[i];
            if(a[i] <= 0) break;
        }
    }

    for(int i = 1; i <= n; ++i){
        if(mt[i]<=0) break;//IMPORTANT!!!!
        for(int j = 1; j <= h; ++j)
            for(int k = 0; k<=mt[i]&&j>=k+t[i-1]; ++k)
                dp[i][j] = max(dp[i][j],dp[i-1][j-k-t[i-1]]+num[i][k]);
    }
    for(int i = 1; i <= n; ++i)
        ans = max(ans,dp[i][h]);
    cout<<ans<<endl;

    return 0;
}
数据来自LOJ
测试点6

输入:
25
15
59 84 39 73 15 84 7 11 63 17 18 49 65 55 19 88 89 68 75 56 69 25 58 89 77
18 32 15 66 2 25 5 5 39 4 7 32 7 8 11 15 0 42 41 31 29 14 32 20 24
1 1 2 2 2 1 1 2 1 2 1 2 1 2 2 1 2 1 1 1 1 1 2 2

输出:
13884

我的答案:
14679

心态崩了,调了两天没调出来,求助各位大佬Orz

请不要无意义回复!!!

2020/6/3 16:53
加载中...