Lawrence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4322 Accepted Submission(s): 1984
Problem Description
T. E. Lawrence was a controversial figure during World War I. He was a British officer who served in the Arabian theater and led a group of Arab nationals in guerilla strikes against the Ottoman Empire. His primary targets were the railroads. A highly fictionalized version of his exploits was presented in the blockbuster movie, "Lawrence of Arabia".
You are to write a program to help Lawrence figure out how to best use his limited resources. You have some information from British Intelligence. First, the rail line is completely linear---there are no branches, no spurs. Next, British Intelligence has assigned a Strategic Importance to each depot---an integer from 1 to 100. A depot is of no use on its own, it only has value if it is connected to other depots. The Strategic Value of the entire railroad is calculated by adding up the products of the Strategic Values for every pair of depots that are connected, directly or indirectly, by the rail line. Consider this railroad:
Its Strategic Value is 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.
Now, suppose that Lawrence only has enough resources for one attack. He cannot attack the depots themselves---they are too well defended. He must attack the rail line between depots, in the middle of the desert. Consider what would happen if Lawrence attacked this rail line right in the middle:
The Strategic Value of the remaining railroad is 4*5 + 1*2 = 22. But, suppose Lawrence attacks between the 4 and 5 depots:
The Strategic Value of the remaining railroad is 5*1 + 5*2 + 1*2 = 17. This is Lawrence's best option.
Given a description of a railroad and the number of attacks that Lawrence can perform, figure out the smallest Strategic Value that he can achieve for that railroad.
Input
There will be several data sets. Each data set will begin with a line with two integers, n and m. n is the number of depots on the railroad (1≤n≤1000), and m is the number of attacks Lawrence has resources for (0≤m<n). On the next line will be n integers, each from 1 to 100, indicating the Strategic Value of each depot in order. End of input will be marked by a line with n=0 and m=0, which should not be processed.
Output
For each data set, output a single integer, indicating the smallest Strategic Value for the railroad that Lawrence can achieve with his attacks. Output each integer in its own line.
Sample Input
4 1
4 5 1 2
4 2
4 5 1 2
0 0
Sample Output
17
2
Source
2009 Multi-University Training Contest 2 - Host by TJU
比較典型的問題，把n個節點分成m塊，使得最後價值最小。
根據題意，很容易得出dp方程：dp[i][j]=dp[i-1][k]+sigma(sigma(a[l]*a[p]))(k<l<p<=j)，兩個sigma分别對l和p求和，其中dp[i][j]表示前j個點，分成i段的最小價值。轉換一下式子，引入兩個新數組可得：dp[i][j]=d[i-1][k]+c[j]-c[k]-s[k]*(s[j]-s[k])，其中c[i]表示a中從1~i任意兩個數乘積的和，s[i]表示a的字首和。我們發現，分别枚舉i、j和k，時間複雜度為O（MN^2）顯然不能接受。
于是我們的第一種解決方案就是對式子變形，看是否能用斜率優化。還是老套路，假設決策k優于決策l，且有k>l，則dp[i-1][k]+c[j]-c[k]-s[k]*(s[j]-s[k])<dp[i-1][l]+c[j]-c[l]+s[l]*(s[j]-s[l])，化簡移項可得dp[i-1][k]-c[k]+s[k]^2-(dp[i-1][l]-c[l]+s[l]^2)<s[j]*(s[k]-s[l])。又s[i]單調遞增，是以有當k優于l時，斜率K<s[j]。故我們每次找一個最優的決策k，使得他對任意l<k，都有斜率小于s[j]，是以要維護一個相鄰兩點斜率單調遞增的向右下凸出的凸包。值得注意的是，由于題目要求，當分成i塊時，點的個數至少為i+1，故初始隊列中就要包含一個決策i，而不是0。具體見代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
#define N 1100
using namespace std;
long long s[N],a[N],c[N],q[N],dp[N][N];
int h,t,n,m,p,i,j;
double getdp(int k)
{
return dp[i-1][k]+c[j]-c[k]-s[k]*(s[j]-s[k]);
}
long long Y(int k)
{
return dp[i-1][k]+s[k]*s[k]-c[k];
}
long long X(int x)
{
return s[x];
}
bool judge(int l,int k,int j)
{
return (Y(k)-Y(l))<=(X(k)-X(l))*s[j];
}
bool maintain(int k,int i,int j)
{
return (Y(k)-Y(i))*(X(j)-X(k))>=(Y(j)-Y(k))*(X(k)-X(i));
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n+m)
{
for(int i=1;i<=n;i++)
{
scanf("%I64d",&a[i]);
s[i]=a[i]+s[i-1];
c[i]=c[i-1]+a[i]*s[i-1];
}
memset(dp,INF,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
dp[0][i]=c[i];
for(i=1;i<=m;i++)
{
h=t=0; q[0]=i; //初始時，把決策i加入隊列
for(j=i+1;j<=n;j++) //循環從i+1開始
{
while (h<t && judge(q[h],q[h+1],j)) h++;
dp[i][j]=getdp(q[h]);
while (h<t && maintain(q[t],q[t-1],j)) t--;
q[++t]=j;
}
}
printf("%I64d\n",dp[m][n]);
}
return 0;
}
其實，斜率優化最近講的夠多了，如果單單隻是斜率優化，這道題目可能不值得我寫一篇博文。是以很顯然還有另外一種方法。
第二種解決方案就是四邊形優化了，其實我當時總結四邊形優化的時候就想找一道題既能夠用四邊形優化，也能夠用斜率優化，但沒找到，沒想到這次發現了意外之喜。稍微回顧一下四邊形優化。首先，他的使用條件是dp數組是由一個滿足四邊形不等式的w數組相加得來的，即dp數組也滿足四邊形不等式。這樣的話，對于目前狀态i、j，dp[i][j]取最有的決策，就在s[i-1][j]到s[i,j-1]之間。如此一來，決策的枚舉數量大大減少，達到了優化的效果。
聯系到這一題，很容易看出dp[i][j]=d[i-1][k]+w[k+1][j]。其中這個w[i][j]表示，從i~j所有數字為一段産生的價值。這個很容易可以通過預處理算出來。然後dp數組顯然也是由w數組構成的。現在的問題就是，如何判定w[i][j]是否滿足四邊形不等式。其實我也沒什麼好方法，網上有一種：如果（w[i+1][j]-w[i][j]）關于j單調遞減，那麼w[i][j]就滿足四邊形不等式，它的證明和正确性都不得而知，但是既然有人這麼說，那麼再稍微找幾個數字驗算一下，沒有問題就直接用吧。是以就直接用了，對于每一個狀态記錄一個決策數組，把每次選取的決策記錄下來，作為後面狀态決策選取的範圍。具體見代碼：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 1010
using namespace std;
long long w[N][N],dp[N][N],a[N],sum[N],c[N];
int s[N][N],n,m;
int main()
{
while(~scanf("%d%d",&n,&m)&&n+m)
{
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=a[i]+sum[i-1];
c[i]=c[i-1]+a[i]*sum[i-1];
}
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
w[i][j]=c[j]-c[i-1]-sum[i-1]*(sum[j]-sum[i-1]); //預處理w數組
memset(dp,INF,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[0][i]=w[1][i];
s[0][i]=0;
}
//dp[0][0]=0;
for(int i=1;i<=m;i++)
{
s[i][n+1]=n;
for(int j=n;j>i;j--)
{
int l=s[i-1][j],r=min(j-1,s[i][j+1]); //确定決策枚舉範圍
for(int k=l;k<=r;k++)
if (dp[i][j]>dp[i-1][k]+w[k+1][j])
{
dp[i][j]=dp[i-1][k]+w[k+1][j];
s[i][j]=k; //記錄最優決策
}
}
}
printf("%I64d\n",dp[m][n]);
}
return 0;
}