大家好，又见面了，我是你们的朋友全栈君。
这道题写了我好久， 交上去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
