这道题写了我好久, 交上去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];elsedp[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]
(2)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;
}