【NOIP2016DP专题测试】石子合并加强版

发布于 2016-11-15  435 次阅读


题目大意:给定N堆石子,三堆三堆合并,问消耗的最小值。(一串序列,不是环)(n<=400)


题目分析:沿用经典问题石子合并的方程f[i][j]表示从i到j合并的最小体力值,s[]为预处理的前缀和,则有f[i][j]=min{f[i][k1]+f[k1+1][k2]+f[k2+1][j]+s[j]-s[i-1]}。显然四维方程会TLE。所以观察后考虑将前两个式子合并,即在处理过程中同时计算f2[i][j]=min{f[i][k1]+f[k1+1][j]}。那么f[i][j]=min{f2[i][k2]+f[k2+1][j]}。三维即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;

int f[405][405],f2[405][405],s[405],n,x;

int main(){
	scanf("%d",&n);
	if (!(n&1)){
		printf("Impossible");return 0;
	}
	For (i,n){
		scanf("%d",&x);
		s[i]=s[i-1]+x;
		f2[i][i]=1e9;f[i][i]=0;
	}
	
	ForD (i,n-1)
		Fork (j,i+1,n){
			f[i][j]=f2[i][j]=1e9;
			Fork (k,i,j-1){
				f2[i][j]=min(f2[i][j],f[i][k]+f[k+1][j]);
				f[i][j]=min(f[i][j],f2[i][k]+f[k+1][j]);
			}
			f[i][j]+=s[j]-s[i-1];	
		}	
	printf("%d",f[1][n]);
}

「知我罪我,其惟春秋」