#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
请不要无意义回复!!!