UVA 10003 Cutting Sticks (区间DP+四边形不等式）
这题是一个典型的区间DP的问题，用dp[i][j]表示区间i-j内的最优解，最终的答案是dp[0][n+1]
状态转移方程为:
dp[i][j]=min(dp[i][k]+dp[k][j]+该区间的木棍长度,dp[i][j])
如果仅仅是区间DP，状态量为O(n2)，每个状态的决策有O(n)个，则总的时间复杂度为O(n3)。
如果通过四边形不等式优化状态的决策，可以将时间复杂度降低为O(n2)。
使用四边形不等式的前提：
1、d(i,j)+d(i+1,j+1)<=d(i,j+1)+d(i+1,j),其中d(i,j)表示状态量。
也等价于，令f(i,x)=d(i,x)-d(i+1,x)，f(i,x)关于自变量x递增；
也等价于，令f(x,j)=d(x,j+1)-d(x,j)，f(x,j)关于自变量x递减;
2、状态转移方程有类似形式：
dp(i,j)=min(d(i,k)+d(k,j)+w(i,j,k))
四边形不等式结论：
s(i,j-1)<=s(i,j)<=s(i+1,j),其中s(i,j)表示d(i,j)的最佳决策点，具体证明过程详见：
https://blog.csdn.net/qq_41695941/article/details/83025188
AC代码如下：
#include<bits/stdc++.h>
using namespace std;
int l,n;
int point[55];
int dp[55][55];
int si[55][55];
int solve(void)
{memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++){dp[i-1][i]=0;si[i-1][i]=i;}for(int s=2;s<=n;s++){for(int i=0;i<=n-s;i++){int j=i+s;for(int k=si[i][j-1];k<=si[i+1][j];k++)if(dp[i][j]>dp[i][k]+dp[k][j]+point[j]-point[i]){dp[i][j]=dp[i][k]+dp[k][j]+point[j]-point[i];si[i][j]=k;}}}return dp[0][n];
}
int main(void)
{
// freopen("out.txt","w",stdout);point[0]=0;while(~scanf("%d",&l)&&l){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&point[i]);point[++n]=l;printf("The minimum cutting is %d.\n",solve());}
// fclose(stdout);
}
//100
//3
//25 50 75
//10
//4
//4 5 7 8
//0