NYOJ737石子合并
狀态:dp[i][j] 表示i..j堆石子合并成一堆，所需最小力氣值
狀态轉移方程:dp[i][j]=min(dp[i][j-k]+dp[j-k+1][j]) +sum[i][j]條件:j-k>=i,k>=0
求解：dp[1][n]
#include<stdio.h>
#define M 201
#define INF 1000000000
int n,f[M][M],sum[M][M],stone[M];
int main()
{
int i,j,k,t;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&stone[i]);
for(i=1;i<=n;i++)
{
f[i][i]=0;
sum[i][i]=stone[i];
for(j=i+1;j<=n;j++)
sum[i][j]=sum[i][j-1]+stone[j];
}
for(int len=2;len<=n;len++)//歸并的石子長度
{
for(i=1;i<=n-len+1;i++)//i為起點，j為終點
{
j=i+len-1;
f[i][j]=INF;
for(k=i;k<=j-1;k++)//分割點
{
if(f[i][j]>f[i][k]+f[k+1][j]+sum[i][j])
f[i][j]=f[i][k]+f[k+1][j]+sum[i][j];
}
}
}
printf("%d\n",f[1][n]);
}
return 0;
}
NKOJ 圓形操場
法一：
在一個圓形操場的四周擺放着n 堆石子。現要将石子有次序地合并成一堆。規
定每次隻能選相鄰的2 堆石子合并成新的一堆，并将新的一堆石子數記為該次合并的得分。試設計一個算法，計算出将n堆石子合并成一堆的最小得分和最大得分。
程式設計任務：
對于給定n堆石子,程式設計計算合并成一堆的最小得分和最大得分。
DP：因為石子繞成一個環，不是一條直線，是以dp[i][j]的含義應為從第i堆開始，合并j堆石子能得到的最優值
則易得狀态轉移方程為
dp1[i][j]=better(dp1[i][j],dp1[i][k]+dp1[(i+k-1)%n+1][j-k]+sum[i][j]);
#include<stdio.h>
#include<string.h>
const int INF = 1000000000;
#define M 110
int dp1[M][M],dp2[M][M];
int sum[M][M];
int num[M];
int min(int a,int b)
{
return a<b?a:b;
}
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
for(i=1;i<=n;i++)
sum[i][1]=num[i];
for(j=2;j<=n;j++)
for(i=1;i<=n;i++)
sum[i][j]=sum[i%n+1][j-1]+num[i];
for(i=0;i<=n;i++)
dp1[i][1]=dp2[i][1]=0;
for(j=2;j<=n;j++)
{
for(i=1;i<=n;i++)
{
dp1[i][j]=0;
dp2[i][j]=INF;
for(k=1;k<j;k++)
{
dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[(i+k-1)%n+1][j-k]+sum[i][j]);
dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[(i+k-1)%n+1][j-k]+sum[i][j]);
}
}
}
int ansmi=INF,ansmx=0;
for(i=1;i<=n;i++)
{
ansmx=max(ansmx,dp1[i][n]);
ansmi=min(ansmi,dp2[i][n]);
}
printf("%d\n%d\n",ansmi,ansmx);
}
return 0;
}
法二：轉
這道題有一個要注意的地方，那就是紅字标注的圓形操場。因為石堆是圓形的，是以有n種合并方式，需要增加一層循環來依次枚舉起始堆。這樣，會大大增加時間複雜度。
解題思路是動态規劃，不經優化的動态規劃的時間複雜度是O(n^3)，如果再套一層循環，那麼肯定會TLE。
是以需要進行優化。
首先可以構造如下的數組：
a[0],a[1],...,a[n-1],a[n],a[n+1],...,a[2n-2]
即：
a[0],a[1],...,a[n-1],a[0],a[1],...,a[n-2]
這樣，經過一次DP就可以算出最值，進而去掉了循環，降低了一個次元。
對于DP，最小值可以用四邊形不等式優化。注意：求最大值不能用四邊形不等式，因為最大值不滿足單調性，但最大值有一個性質，即總是在兩個端點的最大者中取到。
即max[i][j] = max{max[i][j-1],max[i+1][j]| + sum[i][j] (sum[i][j]是第i堆到第j堆的石子總數)
經過優化，算法複雜度可以減少至O(n^2)。
#include
#define MAXN 200
#define MAX_INT 0x7fffffff;
#define MIN_INT 0xffffffff;
int sum[MAXN][MAXN];
int s[MAXN][MAXN]; //最小值決策量s
int max[MAXN][MAXN];
int min[MAXN][MAXN];
int mmin,mmax;
void MergeStone(int n)
{
int i,j,k,r; //r表示間距
mmin = MAX_INT;
mmax = MIN_INT;
for(r = 2; r <= n; r++) //計算第i堆到第j堆的總石子數 間距到n為止
{
for (i = 0; i < 2*n-r; i++)
{
j = i + r - 1;
sum[i][j] = sum[i][j-1] + sum[j][j];
min[i][j] = MAX_INT;
for (k = s[i][j-1]; k <= s[i+1][j]; k++)
{
int t = min[i][k] + min[k+1][j] + sum[i][j];
if (t
{
min[i][j] = t;
s[i][j] = k;
}
}
if (max[i][j-1] > max[i+1][j])
max[i][j] = max[i][j-1] + sum[i][j];
else
max[i][j] = max[i+1][j] + sum[i][j];
if (i == (j+1)%n)
{
if(max[i][j] > mmax)
mmax = max[i][j];
if(min[i][j] < mmin)
mmin = min[i][j];
}
}
}
}
int main()
{
int n,i;
while(scanf("%d",&n) && n)
{
mmax = 0;
mmin = 0;
for(i=0; i
{
scanf("%d",&sum[i][i]);
min[i][i] = 0;
max[i][i] = 0;
s[i][i] = i;
}
for(i=n; i<2*n-1; i++)
{
min[i][i] = 0;
max[i][i] = 0;
s[i][i] = i;
sum[i][i] = sum[i%n][i%n];
}
if (n>1)
MergeStone(n);
printf("%d %d\n",mmin,mmax);
}
return 0;
}