一种基于决策单调性的写法
  • 板块学术版
  • 楼主rand_Zq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 21:59
  • 上次更新2024/8/21 09:21:50
查看原帖
一种基于决策单调性的写法
901086
rand_Zq楼主2024/8/20 21:59
这是正确的

for(int i=1;i<=n;i++){
        dp[1][i]=w(1,i);
    }
    for(int k=2;k<=m;k++){
        pos[k][n+1]=n;
        for(int i=n;i>=1;i--){
            dp[k][i]=2e9;
            for(int j=max(2,pos[k-1][i]);j<=min(pos[k][i+1],i);j++){
                if(dp[k-1][j-1]+w(j,i)<dp[k][i]){
                    dp[k][i]=dp[k-1][j-1]+w(j,i),pos[k][i]=j;
                }
            }
        }
    }
但我什么我对pos[1][i]=i这样写就错了
2024/8/20 21:59
加载中...