rt,一下代码通过了测试:
#include<bits/stdc++.h>
using namespace std;
const int maxn=50,maxt=250;
const int inf=24304089;
inline int read()
{
register int x=0;
register char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
int n,T;
int f[maxt][maxn][maxt];
int d[maxn],chu[maxn],jian[maxn];
int main()
{
n=read(),T=read()*12;
for(register int i=1;i<=n;i++)
chu[i]=read();
for(register int i=1;i<=n;i++)
jian[i]=read();
for(register int i=1;i<n;i++)
d[i]=read();
memset(f,128,sizeof(f));
for(register int i=0;i<=T;i++)
for(register int j=0;j<=T;j++)
f[i][0][j]=0;
f[0][1][0]=0;
for(register int i=1;i<=T;i++)
{
for(register int j=1;j<=n;j++)
{
if(i-d[j-1]<0) continue;
for(register int u=1;u<=T;u++) f[i][j][0]=max(f[i][j][0],f[i-d[j-1]][j-1][u]);
for(register int u=1;u<=T;u++)
{
f[i][j][u]=f[i-1][j][u-1];
f[i][j][u]+=max(chu[j]-(u-1)*jian[j],0);
}
}
}
register int ans=0;
for(register int j=1;j<=n;j++)
for(register int i=1;i<=T;i++)
ans=max(ans,f[T][j][i]);
cout<<ans<<endl;
return 0;
}
Hack 数据:
22
12
9 51 13 98 2 88 76 81 95 18 41 56 88 58 28 87 19 79 68 27 79 42
7 13 8 1 2 6 24 19 78 3 38 38 31 44 15 43 12 19 28 8 71 9
4 95 28 58 43 56 24 82 41 75 4 27 99 98 37 64 31 37 56 28 18
rightans:1530
myans:1354
少转移了一个状态也能过.....
错误代码如下:
#include<bits/stdc++.h>
using namespace std;
const int maxn=50,maxt=250;
const int inf=24304089;
inline int read()
{
register int x=0;
register char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
int n,T;
int f[maxt][maxn][maxt];
int d[maxn],chu[maxn],jian[maxn];
int main()
{
n=read(),T=read()*12;
for(register int i=1;i<=n;i++)
chu[i]=read();
for(register int i=1;i<=n;i++)
jian[i]=read();
for(register int i=1;i<n;i++)
d[i]=read();
memset(f,128,sizeof(f));
for(register int i=0;i<=T;i++)
for(register int j=0;j<=T;j++)
f[i][0][j]=0;
f[0][1][0]=0;
for(register int i=1;i<=T;i++)
{
for(register int j=1;j<=n;j++)
{
if(i-d[j-1]<0) continue;
for(register int u=1;u<=T;u++)//就是这里,应该从 u=0 开始转移
f[i][j][0]=max(f[i][j][0],f[i-d[j-1]][j-1][u]);
for(register int u=1;u<=T;u++)
{
f[i][j][u]=f[i-1][j][u-1];
f[i][j][u]+=max(chu[j]-(u-1)*jian[j],0);
}
}
}
register int ans=0;
for(register int j=1;j<=n;j++)
for(register int i=1;i<=T;i++)
ans=max(ans,f[T][j][i]);
cout<<ans<<endl;
return 0;
}
是的我用的方法和所有题解都不一样qwq