題目大意：給定一個長度為n的序列，至多將序列分成m段，每段序列都有權值，權值為序列內兩個數兩兩相乘之和。m<=n<=1000.
解題思路：經典的DP優化題，可以用四邊形不等式優化也可以用斜率優化，我三種方法實現，兩種斜率優化，一種四邊形不等式，其中復雜度都為n*m，但是常熟略有差異。
狀態轉移方程很好想，dp[i][j] = min(dp[i][j],dp[k][j-1]+cost[k+1][j])(1<=k<i),這種方程普通寫法是n*n*m，當n為1000時運算量為10億級別，必須優化。
第一種：四邊形不等式優化，這種方法是最簡單的，主要是減少枚舉k的次數。cost[i][j]是某段區間的權值，當區間變大，權值也隨之變大，區間變小，權值也隨之變小，此時就可以用四邊形不等式優化。
我們設s[i][j]為dp[i][j]的前導狀態，即dp[i][j] = dp[s[i][j][j-1] + cost[s[i][j]+1][j].之後我們枚舉k的時候只要枚舉s[i][j-1]<=k<=s[i+1][j],此時j必須從小到大遍歷，i必須從大到小。
用這種方法我的代碼跑了140ms。
第二種：斜率優化.其實是借鑒大牛大思路，Here，我只是拋磚引玉而已。這種方法的dp和suma數組必須為64位整數，因為平方和會超過32位整數。
用這種方法我的代碼跑了350ms。
第三種:斜率優化.其實是借鑒大牛大思路，Here，我只是拋磚引玉而已。其實這題可以作為模板題，斜率優化大抵如此吧。
用這種方法我的代碼跑了109ms。
測試數據：
Input:
4 1
4 5 1 2
4 2
4 5 1 2
5 3
1 2 1 2 1
6 4
7 5 3 6 8 9
10 3
1 4 2 7 5 6 8 5 6 9
OutPut:
17
2
92
15
187
C艹代碼：
[cpp]
//四邊形不等式
#include <stdio.h>
#include <string.h>
#define MAX 1100
#define INF (1<<30)
int n,m,sum[MAX],cost[MAX][MAX];
int arr[MAX],dp[MAX][MAX],s[MAX][MAX];
void Initial() {
int i, j, k;
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (j < i) cost[i][j] = 0;
else cost[i][j] = cost[i][j - 1] + arr[j] * (sum[j - 1] - sum[i - 1]);
for (i = 0; i <= n; ++i) {
dp[i][0] = cost[1][i];
s[i][0] = 0,s[n+1][i] = n;
}
}
int Solve_DP() {
int i,j,k;
for (j = 1; j <= m; ++j)
for (i = n; i >= 1; --i) {
dp[i][j] = INF;
for (k = s[i][j-1] ; k <= s[i+1][j]; ++k)
if (dp[k][j-1] + cost[k+1][i] < dp[i][j]) {
s[i][j] = k;
dp[i][j] = dp[k][j-1] + cost[k+1][i];
}
}
return dp[n][m];
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n+m) {
for (i = 1; i <= n; ++i)
scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
Initial();
int ans = Solve_DP();
printf("%I64d\n",ans);
}
}
[cpp]
//sum[i] = arr[1] + .. arr[i]^2
//sum2[i] = arr[1]^2 + .. arr[i]^2;
//dp[i][j] = min{dp[k][j-1] -sum[i] * sum[k] + (suma[k] - sum[k]^2)/2 + (sum[k]^2 - suma[k])/2};
//斜率優化二
#include <stdio.h>
#include <string.h>
#define MAX 1100
#define INF (1<<30)
#define int64 __int64//long long
struct point {
int64 x,y;
}pot[MAX];
int head,tail,qu[MAX];
int n,m,arr[MAX];
int64 sum[MAX],sum2[MAX],dp[MAX][MAX];
void Initial() {
for (int i = 1; i <= n; ++i) {
sum[i] = arr[i] + sum[i-1];
sum2[i] = arr[i] * arr[i] + sum2[i-1];
dp[i][0] = dp[i-1][0] + arr[i] * sum[i-1];
}
}
int CheckIt(point p0,point p1,point p2) {
return (p0.x-p1.x) * (p0.y-p2.y) - (p0.y-p1.y) * (p0.x-p2.x) <= 0;
}
int NotBest(point p0,point p1,int k) {
return p0.y - k * p0.x > p1.y - k * p1.x;
}
int Solve_DP() {
int i,j,k;
for (j = 1; j <= m; ++j) {
head = 0,tail = 0;
qu[tail] = 0;
for (i = j + 1; i <= n; ++i) {
pot[i].x = sum[i-1];
pot[i].y = dp[i-1][j-1] + (sum[i-1] * sum[i-1] + sum2[i-1]) / 2;
while (head <= tail - 1 &&
CheckIt(pot[qu[tail-1]],pot[qu[tail]],pot[i])) tail--;
qu[++tail] = i;
while (head + 1 <= tail &&
NotBest(pot[qu[head]],pot[qu[head+1]],sum[i])) head++;
k = qu[head];
//dp[i][j] = y - k * x + c
dp[i][j] = pot[k].y - sum[i] * pot[k].x + (sum[i] * sum[i] - sum2[i]) / 2;
}
}
return dp[n][m];
}
int GetInt() {
char ch = ' ';
while (ch < '0' || ch > '9')
ch = getchar();
int x = 0;
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0',ch = getchar();
return x;
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n+m) {
for (i = 1; i <= n; ++i)
scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
Initial();
int ans = Solve_DP();
printf("%d\n",ans);
}
}
[cpp]
//cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])
//dp[i][j]=dp[k][j-1]+cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])
// =dp[k][j-1]-cost[1][k]+sum[k]^2-sum[i]*sum[k]+cost[1][i]
//斜率優化一
#include <stdio.h>
#include <string.h>
#define MAX 1100
#define INF (1<<30)
struct point {
int x,y;
}pot[MAX];
int head,tail,qu[MAX];
int n,m,arr[MAX],cost[MAX];
int sum[MAX],sum2[MAX],dp[MAX][MAX];
void Initial() {
for (int i = 1; i <= n; ++i) {
sum[i] = arr[i] + sum[i-1];
cost[i] = cost[i-1] + arr[i] * sum[i-1];
dp[i][0] = cost[i];
}
}
int CheckIt(point p0,point p1,point p2) {
return (p0.x-p1.x) * (p0.y-p2.y) - (p0.y-p1.y) * (p0.x-p2.x) <= 0;
}
int NotBest(point p0,point p1,int k) {
return p0.y - k * p0.x > p1.y - k * p1.x;
}
int Solve_DP() {
int i,j,k;
for (j = 1; j <= m; ++j) {
head = 0,tail = 0;
qu[tail] = 0;
for (i = j + 1; i <= n; ++i) {
pot[i].x = sum[i-1];
pot[i].y = dp[i-1][j-1] - cost[i-1] + sum[i-1] * sum[i-1];
while (head <= tail - 1 &&
CheckIt(pot[qu[tail-1]],pot[qu[tail]],pot[i])) tail--;
qu[++tail] = i;
while (head + 1 <= tail &&
NotBest(pot[qu[head]],pot[qu[head+1]],sum[i])) head++;
k = qu[head];
//dp[i][j] = y - k * x + c
dp[i][j] = pot[k].y - sum[i] * pot[k].x + cost[i];
}
}
return dp[n][m];
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m),n+m) {
for (i = 1; i <= n; ++i) www.2cto.com
scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
Initial();
int ans = Solve_DP();
printf("%d\n",ans);
}
}
