此题数据微水
  • 板块P1717 钓鱼
  • 楼主lzqy_
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/6/5 14:36
  • 上次更新2023/11/4 22:18:10
查看原帖
此题数据微水
288716
lzqy_楼主2021/6/5 14:36

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

2021/6/5 14:36
加载中...