社区讨论
从上到下的dp错哪了?
P1544三倍经验参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi3yj93w
- 此快照首次捕获于
- 2025/11/18 10:31 4 个月前
- 此快照最后确认于
- 2025/11/18 23:51 4 个月前
如题,dp数组定义和题解一样,但是我是从上往下更新状态,获得30分,我不知道p的那一维究竟要从大到小更新还是从小到大更新
以及有没有人能总结出啥时候从大到小枚举,啥时候又反过来?
代码有注释,求调
CPP#include<bits/stdc++.h>
using namespace std;
#define INF 9e18
int n, k, a[110][110];
long long b[110][110], dp[2][110][5100], ans = -INF;
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
{
cin >> a[i][j];
b[i][j] = a[i][j] * 3;
}
//输入,用b数组表示3倍
for(int i = 0; i <= k; i++)
if(i == 0) dp[1][1][i] = a[1][1];
else dp[1][1][i] = b[1][1];
//初始化第一行第一列
for(int i = 2; i <= n; i++)
for(int j = 1; j <= i; j++)
for(int p = k; p >= 1; p--) //p由大到小
{
if(j == 1)
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j][p] + a[i][j], dp[(i - 1) % 2][j][p - 1] + b[i][j]);
//第一列时只能从上一行对应列转移
else if(j == i)
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j - 1][p] + a[i][j], dp[(i - 1) % 2][j - 1][p - 1] + b[i][j]);
//最后一列只能从上一行前一列转移
else
{
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j][p] + a[i][j], dp[i % 2][j][p]);
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j][p - 1] + b[i][j], dp[i % 2][j][p]);
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j - 1][p] + a[i][j], dp[i % 2][j][p]);
dp[i % 2][j][p] = max(dp[(i - 1) % 2][j - 1][p - 1] + b[i][j], dp[i % 2][j][p]);
}
//非特殊列则有四种转移情况
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++)
ans = max(ans, dp[n % 2][i][j]);
//ans已经初始化为负无穷,同时也枚举了k的值
cout << ans;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...