UVA 10003 Cutting Sticks——四边形不等式优化dp

UVA 10003 Cutting Sticks——四边形不等式优化dp

不能用单调队列做的原因是切割点固定

很明显小区间的权值小于大区间，交错区间的权值等于两区间的交加上两区间的并，权值满足区间包含的单调性，状态满足四边形不等式性质，所以第三重循环可以优化，设s【i】【j】为区间【i，j】的最优切割点，那么求解dp【i】【j】时只需要遍历s【i】【j-1】~s【i+1】【j】即可，复杂度为n^2

#include #include #include #include using namespace std;const int maxn = 100;const int INF = 0x3f3f3f3f;int L, n, p[maxn], s[maxn][maxn], dp[maxn][maxn];int main() { while (~scanf("%d", &L) && L) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &p[i]); p[0] = 0, p[n+1] = L; memset(dp, INF, sizeof(dp)); for (int i = 0; i <= n; i++) dp[i][i] = 0, s[i][i] = i; for (int len = 2; len <= n+1; len++) { for (int i = 0; i+len-1 <= n; i++) { int j = i+len-1; for (int k = s[i][j-1]; k <= s[i+1][j]; k++) { if (dp[i][k]+dp[k+1][j]+p[j+1]-p[i] < dp[i][j]) { dp[i][j] = dp[i][k]+dp[k+1][j]+p[j+1]-p[i]; s[i][j] = k; } } } } printf("The minimum cutting is %d.\n", dp[0][n]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。