社区讨论

从上到下的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 条回复,欢迎继续交流。

正在加载回复...