DP如何优化 玄关

学术版

JimmyDong @ 2024-08-10 15:01:40

for(int i=1;i<=c;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=lim[i];k++)
            {
                if(j-k<0) break;
                f[i][j]=max(f[i][j],f[i-1][j-k]+tg[i][k]);
            }   
        }
    }

现在 c,m,lim[i]<=5000

by Hagasei @ 2024-08-10 15:23:36

minkowski 和。

by Hagasei @ 2024-08-10 15:24:25

如果 tg_i(k) 有凸性

by _LRH_ @ 2024-08-13 15:44:37

@JimmyDong 用单调队列

|