比如
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
dp[i][j]=dp[i-1][j];
}
for(int l=max(1,s[i]-l[i]+1);l<=s[i];l++){
for(int r=s[i];r<=min(n,l+l[i]-1);r++){
dp[i][r]=max(dp[i][r],dp[i-1][l-1]+p[i]*(r-l+1));
}
}
}
这个dp显然可以优化,但是这个不好优化,因为我的方程是dp[i][r]=......,然而i在第一层循环,而r在第三层循环,中间加了一个l。但是我们只要将二三两层循环调换位置就可以了。
又比如
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
dp[i][j]=dp[i-1][j];
}
for(int len=1;len<=l[i];len++){
for(int l=max(1,s[i]-len+1);(l<=s[i])&&(l+len-1<=n);l++){
int r=l+len-1;
dp[i][r]=max(dp[i][r],dp[i-1][l-1])+p[i]*len;
}
}
}
这个和上面一样,但是这个也不好优化,虽然也有上面的问题,但是这个还有一个问题。可以看到这里的r是通过len和l间接求出来的,这样显然是不好的,所以dp里面的东西一定要在循环上枚举。
标签:这个,技巧,int,POJ1821,循环,优化,dp From: https://www.cnblogs.com/wuhupai/p/18042787