caioj 1079 动态规划入门（非常规DP3：钓鱼）(动规中的坑)「建议收藏」

全栈程序员-站长 • 2022年4月20日下午2:00 • 未分类 • 阅读 55

大家好，又见面了，我是你们的朋友全栈君。

这道题写了我好久，交上去90分，就是死活AC不了

后来发现我写的程序有根本性的错误，90分只是数据弱

#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 2123;
int dp[MAXN][MAXN], t[MAXN]; 
int f[MAXN], d[MAXN], h, n;

int main()
{
	scanf("%d%d", &n, &h);
	h *= 12;
	REP(i, 1, n + 1) scanf("%d", &f[i]);
	REP(i, 1, n + 1) scanf("%d", &d[i]);
	REP(i, 1, n) scanf("%d", &t[i]);
	
	REP(i, 0, h + 1) dp[0][i] = 0;
	REP(i, 0, n + 1) dp[i][0] = 0;
	REP(i, 1, n + 1)
	{
		int fish = f[i];
		REP(j, 1, h + 1)
		{
			if(j-t[i-1] > 0 && dp[i-1][j-t[i-1]] > dp[i][j-1] + fish)
				dp[i][j] = dp[i-1][j-t[i-1]], fish = f[i];
			else
				dp[i][j] = dp[i][j-1] + fish, fish = max(fish - d[i], 0);	
		}
	}
	printf("%d\n", dp[n][h]);
	
	return 0;
}

我一开始的程序是这样的，但是又非常多的问题

（1）我这个程序是以最后一个池塘为i定义的，所以应该是max(dp[i][h])，答案不一定是dp[n][h]

（２）dp[i][0] = 0有点问题，因为这个时候不是为0的，只有1是起点。这个时候就相当于每个点都可以是
起点了。应该是dp[0][0] = 0，其他未负无穷。有意义的设为0，其他为负无穷。

正解应该是枚举当前这个池塘钓的时间和上个池塘钓的时间，取最优。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 212;
int dp[MAXN][MAXN * 10], t[MAXN]; 
int diao[MAXN][MAXN], f[MAXN], d[MAXN], h, n;

int main()
{
	scanf("%d%d", &n, &h);
	h *= 12;
	REP(i, 1, n + 1) scanf("%d", &f[i]);
	REP(i, 1, n + 1) scanf("%d", &d[i]);
	REP(i, 1, n) scanf("%d", &t[i]);
	
	REP(i, 1, n + 1)
	{
		diao[i][0] = 0;
		int fish = f[i];
		REP(j, 1, h + 1)
		{
			diao[i][j] = diao[i][j-1] + fish;
			fish = max(fish - d[i], 0);
		}
	}
	
	memset(dp, -63, sizeof(dp));
	int ans = 0;
	REP(i, 0, h + 1) dp[0][i] = 0;
	REP(i, 1, n + 1)
		REP(j, t[i-1], h + 1)
			REP(k, 0, j - t[i-1] + 1)
			{
				dp[i][j] = max(dp[i][j], dp[i-1][k] + diao[i][j-t[i-1]-k]);
				ans = max(ans, dp[i][j]);
			}
	printf("%d\n", ans);
	
	return 0;
}

转载于:https://www.cnblogs.com/sugewud/p/9819421.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107345.html原文链接：https://javaforall.net