关于此题的疑问
  • 板块P1717 钓鱼
  • 楼主czy0323
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/28 23:34
  • 上次更新2023/10/27 01:02:51
查看原帖
关于此题的疑问
538427
czy0323楼主2022/11/28 23:34

如果数据是这样的:

3
1
10 15 50
0 3 4
1 2

那么不应该是先花15分钟到第3个湖,然后花45分钟都在第3个湖钓鱼,钓到的比较多吗?

一共是50+46+42+38+34+30+26+22+18=306条

但是如果用题解第一篇的动态规划算法,算出来的是298?这是怎么回事?有没有大佬解答一下?

顺便帮我看看我的代码为什么不行呗,306这个答案就是用我的代码算出来的

#include<iostream> 
using namespace std;
int n,h;
int f[30],d[30],t[30],dp[30][200],flag[30][200];

int main(){
	cin>>n>>h;
	h=h*12;
	for(int i=1;i<=n;i++)
		cin>>f[i];
	for(int i=1;i<=n;i++)
		cin>>d[i];
	for(int i=2;i<=n;i++){
		cin>>t[i];
		t[i]+=t[i-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=h;j++){
			int pos;
			dp[i][j]=dp[i-1][j],pos=flag[i-1][j];
			for(int k=1;k<=j;k++){
				int times=max(0,k-(t[i]-t[flag[i-1][j-k]]));
				if( d[i]!=0 )
					times=min(times,f[i]/d[i]+1);
				if( dp[i-1][j-k]+times*f[i]-d[i]*times*(times-1)/2>=dp[i][j] )
					dp[i][j]=dp[i-1][j-k]+times*f[i]-d[i]*times*(times-1)/2,pos=i;
			}
			flag[i][j]=pos;
		}
	}
	cout<<dp[n][h];
	return 0;
}
2022/11/28 23:34
加载中...