背景

xq和他的老婆xz最近开了一家花店，他们准备把店里最好看的花都摆在橱窗里。但是他们有很多花瓶，每个花瓶都具有各自的特点，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果。为了使橱窗里的花摆放的最合适，他们得想个办法安排每种花的摆放位置。
可是因为xq和xz每天都太忙，没有时间设计橱窗里花的摆法，所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。

描述

    每种花都有一个标识，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。

    每种花放在不同的瓶子里会产生不同的美观程度，美观程度可能是正数也可能是负数。

    上述例子中，花瓶与花束的不同搭配所具有的美观程度，如下表所示：

                             花    瓶

                      1     2    3    4    5
       1 (杜鹃花)     7    23   -5  -24   16
       2 (秋海棠)     5    21   -4   10   23
       3 (康乃馨)    -21    5   -4  -20   20

    根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。

    为取得最大美观程度，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值，并求出每种花应该摆放的花瓶的编号。

输入格式

第1行：两个整数F和V，表示xq和xz一共有F种花，V个花瓶。(1<=F<=V<=100)
第2行到第F+1行：每行有V个数，表示花摆放在不同花瓶里的美观程度值value。(美观程度和不超过maxint，美观程度有正有负)

输出格式

输出有两行：第一行为输出最大美观程度和的值，第二行有F个数表示每朵花应该摆放的花瓶的编号。若有多种方案，输出字典序较小的（美观程度不变的情况下，花尽量往前放）

样例输入

3 5 
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

样例输出

53
2 4 5

        </article>

这道题其实很明显是一道DP题。
我们不妨设dp[i][j]表示前i束花放在第j个瓶(或最大为j编号的瓶)中的最大美学值。
那么我们便可以用三重循环枚举，第一重循环枚举花束，第二重循环枚举瓶数，第三重循环枚举之前的花瓶
那么我们便可以得到以下方程
dp[i][j]=max(dp[i][j],dp[i-1]][k]+a[i][j]);//k为之前的花瓶
那么我们这里还有一个问题：如何输出瓶数？
这里，我们需要一个数组x，表示在dp的最有值得情况下的瓶子下标
对这个数组进行一系列处理便可

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=101,INF=0x3f3f3f3f;
int n,m,a[N][N],f[N][N],d[N][N],ans[N];
int main(){
	read(n),read(m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j) read(a[i][j]);
	for(int i=1;i<=m-n+1;++i) f[1][i]=a[1][i];
	for(int i=2;i<=n;++i){
		int k=-INF,t;
		for(int j=i;j<=m-n+i;++j){
			if(k<f[i-1][j-1]) k=f[i-1][j-1],t=j-1;
			f[i][j]=k+a[i][j],d[i][j]=t;
		}
	}
	int k=-INF,t;
	for(int i=n;i<=m;++i)
		if(k<f[n][i]) k=f[n][i],t=i;
	printf("%d
",k);
	for(int w=n;t;t=d[w--][t]) ans[w]=t;
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

POJ1952 BUY LOW, BUY LOWER

Description

                    "Buy low; buy lower"

 Day   1  2  3  4  5  6  7  8  9 10 11 12

Price 68 69 54 64 68 64 70 67 78 62 98 87

Day    2  5  6 10

Price 69 68 64 62

Input

Output

Sample Input

12
68 69 54 64 68 64 70 67 78 62
98 87

Sample Output

4 2

Source

如何做到题目中所说的去重呢？方法是若前面出现了一个j，并且a[j]=a[i],f[j]=f[i]就从统计方案数中break。必要性显然。充分性可以注意到这种方式没有完全统计最长的方案数， 而是在相同值处进行了转移的划分。又要实现高精度……时间复杂度(O(n^2 s))

#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=5e3+2;
int n,a[N],f[N],d[N][206];
void work(int x,int y){
	d[x][0]=max(d[x][0],d[y][0]);
	for(int i=1;i<=d[x][0];++i){
		d[x][i]+=d[y][i];
		d[x][i+1]+=d[x][i]/10,d[x][i]%=10;
	}
	if(d[x][d[x][0]+1]) ++d[x][0];
}
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	d[0][0]=d[0][1]=1;
	a[0]=0x7fffffff;
	for(int i=1;i<=n;++i){
		for(int j=i-1;j>=0;--j)
			if(a[j]>a[i]) f[i]=max(f[i],f[j]+1);
		for(int j=i-1;j>=0;--j){
			if(a[j]>a[i]&&f[i]==f[j]+1) work(i,j);
			if(a[i]==a[j]&&f[i]==f[j]) break;
 		}
	}
	int z=0;
	for(int i=1;i<=n;++i) z=max(z,f[i]);
	for(int i=1;i<=n;++i)if(f[i]==z) work(N-1,i);
	printf("%d ",z);
	for(int i=d[N-1][0];i;--i) printf("%d",d[N-1][i]);
	return 0;
}

POJ1934 Trip

Description

Input

Output

Sample Input

abcabcaa
acbacba

Sample Output

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

Source

如何输出方案？方法是使用费严格定义的dp数组，用dfs搜出所有方案。预处理出每个位置之前最近的26个字母的位置，枚举转移搜索。由于每次搜索都查找的是最近的某一个字母，所以不会有重复方案。

#include<iostream>
#include<algorithm>
#include<string>
#define rg register
#define il inline
#define co const
using namespace std;

co int N=106,M=1006,X=26;
int f[N][N],fa[N][X],fb[N][X],t=0,z=0; // base 1
string a,b,s[M];
void dp(int x,int y,string w,int l){
	if((int)w.size()==z){
		s[++t]=w;
		return;
	}
	if(x<0||y<0) return;
	if(a[x]==b[y]){
		dp(x-1,y-1,a[x]+w,l-1);
		return;
	}
	for(int i=0;i<X;++i)
		if(f[fa[x+1][i]][fb[y+1][i]]==l)
			dp(fa[x+1][i]-1,fb[y+1][i]-1,w,l);
}
int main(){
	ios::sync_with_stdio(0);
	cin>>a>>b;
	for(unsigned i=0;i<a.size();++i)
		for(unsigned j=0;j<b.size();++j){
			if(a[i]==b[j]) f[i+1][j+1]=f[i][j]+1;
			else f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
			z=max(z,f[i+1][j+1]);
		}
	for(unsigned i=0;i<a.size();++i)
		for(int j=0;j<X;++j)
			if(a[i]!=j+'a') fa[i+1][j]=fa[i][j];
			else fa[i+1][j]=i+1;
	for(unsigned i=0;i<b.size();++i)
		for(int j=0;j<X;++j)
			if(b[i]!=j+'a') fb[i+1][j]=fb[i][j];
			else fb[i+1][j]=i+1;
	dp(a.size()-1,b.size()-1,"",z);
	sort(s+1,s+t+1);
	for(int i=1;i<=t;++i) cout<<s[i]<<endl;
	return 0;
}

POJ1722 SUBTRACT

Description

con([12,10,4,3,5],2) = [12,6,3,5]

con([12,6,3,5]   ,3) = [12,6,-2]

con([12,6,-2]    ,2) = [12,8]

con([12,8]       ,1) = [4]

Input

Output

Sample Input

5 4
12
10
4
3
5

Sample Output

2
3
2
1

Source

执行n-1次操作后，最后得到的值实际上可以表示成这样：a1 - a2 [] a3 [] a4...... [] an，[]内填上+或者-。

‘+’号操作就是选该元素向左看遇到的第一个‘-’，然后将这个地方先进行t次‘-’，然后再在这之前进行一次‘-’，如，a1-a2+a3+a4就是a1-(a2-a3-a4)，就是先对2这个位置进行2次减法，在对1这个位置进行1次减法。

所以说，用dp[i][j]代表第i位运算结果为j的状态是否可达，并且用pre[i][j]记录它的上一个状态，因为T可正可负，所以需要给j加上一个常数使它变成正数。最后，根据pre数组推算每一个位置是‘+’还是‘-’，再根据上面说的把它全改成‘-’，输出就行了。（如果从右边开始看，开始输出，就不用考虑数组变短所带来的下标偏差了）

#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=106,T=20006,X=10000;
int n,t,a[N],f[N][T],o[N];
int main(){
	read(n),read(t);
	t+=X;
	for(int i=1;i<=n;++i) read(a[i]);
	f[2][a[1]-a[2]+X]=-1;
	for(int i=2;i<n;++i)
		for(int j=0;j<=X<<1;++j)if(f[i][j]){
			if(j+a[i+1]<=X<<1) f[i+1][j+a[i+1]]=1;
			if(j-a[i+1]>=0) f[i+1][j-a[i+1]]=-1;
		}
	for(int i=n;i>1;--i)
		if((o[i]=f[i][t])==1) t-=a[i];
		else t+=a[i];
	int cnt=0;
	for(int i=2;i<=n;++i)
		if(o[i]==1) printf("%d
",i-cnt++-1);
	for(int i=2;i<=n;++i)
		if(o[i]==-1) puts("1");
	return 0;
}

POJ1187 陨石的秘密

Description

公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：
1 1 1 1 6
0 0 6 3 57
8 0 11 3 2845
著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：
1． SS表达式是仅由'{'，'}'，'['，']'，'（'，'）'组成的字符串。
2． 一个空串是SS表达式。
3． 如果A是SS表达式，且A中不含字符'{'，'}'，'['，']'，则(A)是SS表达式。
4． 如果A是SS表达式，且A中不含字符'{'，'}'，则[A]是SS表达式。
5． 如果A是SS表达式，则{A}是SS表达式。
6． 如果A和B都是SS表达式，则AB也是SS表达式。


例如
()(())[]
{()[()]}
{{[[(())]]}}
都是SS表达式。
而
()([])()
[()
不是SS表达式。

一个SS表达式E的深度D(E)定义如下：

例如(){()}[]的深度为2。

密文中的复杂运算是这样进行的：
设密文中每行前4个数依次为L1，L2，L3，D，求出所有深度为D，含有L1对{}，L2对[]，L3对()的SS串的个数，并用这个数对当前的年份11380求余数，这个余数就是密文中每行的第5个数，我们称之为?神秘数?。
密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

Input

Output

Sample Input

1 1 1 2

Sample Output

8

Source

用d[i][j][u][v]表示i个{}，j个[]，u个()，深度为v的序列数，根据最后一个子括号（就是最后一个反括号对应的正括号范围内的括号）分类计数。
最后一个子括号可能深度小于v，此时前面的括号深度必须为v，最后一个子括号深度也可能等于v，此时前面的括号深度可以小于或等于v。
用sum[i][j][u][v]表示i个{}，j个[]，u个()，深度小于等于v的序列数。没递推完i,j,u后，立即计算相应的sum[i][j][u][0…D]的值。
枚举最后一个子括号内有哪些括号完成递推。

有一个直观的转移：套一个括号和两部分合并。
但是这样会有问题：ABC这种SS串会由于合并AB，C和合并A，BC而重复计数。
所以我们换个转移：(A)B，即枚举一部分套一个括号。这样可以同时处理两种情况，不重不漏。

考虑在套最外面的是什么.
若当前枚举到的是i个"()",j个"[]",k个"{}",
那么当最外面是"()"时,方案数就应是(0,0,i−1,d−1)∗(a,b,c−i,d)(a,b,c为dfs时的状态)
而最外面是"[]"时,就是(0,j−1,i,d−1)∗(a,b−j,c−i,d),
同理,最外面是"{}"时,就是(k−1,j,i,d−1)∗(a−k,b−j,c−i,d),

时间复杂度(O((l_1l_2l_3)^2 d))

#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int L=11,D=31,mod=11380;
int f[L][L][L][D],s[L][L][L][D];
int main(){
	int l1,l2,l3,d;
	read(l1),read(l2),read(l3),read(d);
	f[0][0][0][0]=s[0][0][0][0]=1;
	for(int i=0;i<=l1;++i)for(int j=0;j<=l2;++j)for(int k=0;k<=l3;++k){
		for(int l=1;l<=d;++l)if(i+j+k>=l){
			int&x=f[i][j][k][l];
			if(i) x=f[i-1][j][k][l-1];
			else if(j) x=f[0][j-1][k][l-1];
			else if(k) x=f[0][0][k-1][l-1];
			else x=0;
			for(int ii=0;ii<=i;++ii)for(int jj=0;jj<=j;++jj)for(int kk=0;kk<=k;++kk)
				if(ii+jj+kk&&ii+jj+kk!=i+j+k){
					if(ii){
						if(l>=2) x=(x+s[ii-1][jj][kk][l-2]*f[i-ii][j-jj][k-kk][l])%mod;
						x=(x+f[ii-1][jj][kk][l-1]*s[i-ii][j-jj][k-kk][l])%mod;
					}
					else if(jj){
						if(l>=2) x=(x+s[0][jj-1][kk][l-2]*f[i][j-jj][k-kk][l])%mod;
						x=(x+f[0][jj-1][kk][l-1]*s[i][j-jj][k-kk][l])%mod;
					}
					else{
						if(l>=2) x=(x+s[0][0][kk-1][l-2]*f[i][j][k-kk][l])%mod;
						x=(x+f[0][0][kk-1][l-1]*s[i][j][k-kk][l])%mod;
					}
				}
		}
		for(int l=1;l<=d;++l) s[i][j][k][l]=(s[i][j][k][l-1]+f[i][j][k][l])%mod;
	}
	printf("%d
",f[l1][l2][l3][d]);
	return 0;
}

CH5E07 划分大理石

5E07 划分大理石 0x5E「动态规划」练习

描述

有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。 

输入格式

有多组数据！
所以可能有多行
如果有0 0 0 0 0 0表示输入文件结束
其余的行为6个整数

输出格式

有多少行可行数据就有几行输出
如果划分成功，输出Can，否则Can't

样例输入

4 7 4 5 9 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0

样例输出

Can't
Can
Can't
Can't
Can

        </article>

多重背包二进制划分。随便翻了下别人的代码，学习了一种倍增写法。
为什么bitset比循环慢？报警了。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

int a[7];
bitset<60001> f;
int main(){
	while(1){
		int s=0;
		for(int i=1;i<=6;++i) s+=read(a[i])*i;
		if(!s) break;
		if(s&1) {puts("Can't");continue;}
		f.reset();
		f[0]=1;
		for(int i=1;i<=6;++i){
			for(int p=1;a[i]>=p;a[i]-=p) f|=f<<i*p;
			if(a[i]) f|=f<<i*a[i];
		}
		puts(f[s/2]?"Can":"Can't");
	}
	return 0;
}

POJ2176 Folding

Language:Default

Folding

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1928		Accepted: 671		Special Judge

Description

Bill is trying to compactly represent sequences of capital alphabetic characters from 'A' to 'Z' by folding repeating subsequences inside them. For example, one way to represent a sequence AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D. He formally defines folded sequences of characters along with the unfolding transformation for them in the following way:

• A sequence that contains a single character from 'A' to 'Z' is considered to be a folded sequence. Unfolding of this sequence produces the same sequence of a single character itself.
  
• If S and Q are folded sequences, then SQ is also a folded sequence. If S unfolds to S' and Q unfolds to Q', then SQ unfolds to S'Q'.
  
• If S is a folded sequence, then X(S) is also a folded sequence, where X is a decimal representation of an integer number greater than 1. If S unfolds to S', then X(S) unfolds to S' repeated X times.

According to this definition it is easy to unfold any given folded sequence. However, Bill is much more interested in the reverse transformation. He wants to fold the given sequence in such a way that the resulting folded sequence contains the least possible number of characters.

Input

The input contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

Output

Write to the output a single line that contains the shortest possible folded sequence that unfolds to the sequence that is given in the input file. If there are many such sequences then write any one of them.

Sample Input

AAAAAAAAAABABABCCD

Sample Output

9(A)3(AB)CCD

Source

Northeastern Europe 2002

给一个字符串，尽量压缩，让他长度最短。（）和数字都是算长度的。所以样例里CC才没有变成2（C）

能够想到的是子结构是保存区间i，j中最短的串的长度len，以及这个最短的串

状态转移的时候我们有两种操作，一种就是简单的找一个中间的点，把两边的串合并。这个比较简单。

一种是看这个串能如何压缩。于是我们可以去枚举最后压缩了之后的子串的长度，不包括数字和括号。

对于一个区间（i， j）我们从小到大枚举压缩后的子串长度，因为压缩的越小越好。压缩完成后去比较是压缩比较好还是合并比较好。

每一次枚举区间长度和起始点。

#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=106,INF=0x3f3f3f3f;
struct F{
	char s[N];
	int len;
}f[N][N];
char s[N];
int n;
int main(){
	scanf("%s",s),n=strlen(s);
	for(int i=0;i<n;++i) f[i][i].s[0]=s[i],f[i][i].len=1;
	for(int len=2;len<=n;++len)
		for(int l=0;l+len<=n;++l){
			int r=l+len-1;
			f[l][r].len=INF;
			for(int i=1;i<=len>>1;++i)if(len%i==0){
				int L=l,R=l+i;
				while(R<=r&&s[L]==s[R]) ++L,++R;
				if(R>r){
					sprintf(f[l][r].s,"%d(",len/i);
					strcat(f[l][r].s,f[l][l+i-1].s);
					strcat(f[l][r].s,")");
					f[l][r].len=strlen(f[l][r].s);
					break;
				}
			}
			for(int i=l;i<=r;++i)if(f[l][r].len>f[l][i].len+f[i+1][r].len){
				f[l][r].len=f[l][i].len+f[i+1][r].len;
				strcpy(f[l][r].s,f[l][i].s);
				strcat(f[l][r].s,f[i+1][r].s);
			}
		}
	puts(f[0][n-1].s);
	return 0;
}

POJ1191 棋盘分割

Language:Default

棋盘分割

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 16561		Accepted: 5945

Description

将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差，其中平均值，x_i为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。

Input

第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output

仅一个数，为O'（四舍五入精确到小数点后三位）。

Sample Input

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

Sample Output

1.633

Source

Noi 99

这种题打个搜索应该也能过吧。

#include<iostream>
#include<cmath>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int INF=0x3f3f3f3f;
int s[9][9],f[15][9][9][9][9];
int calc(int k,int x1,int y1,int x2,int y2){
	int ans=INF;
	for(int i=x1+1;i<x2;++i){
		ans=min(ans,f[k-1][x1][y1][i][y2]+f[1][i][y1][x2][y2]);
		ans=min(ans,f[k-1][i][y1][x2][y2]+f[1][x1][y1][i][y2]);
	}
	for(int i=y1+1;i<y2;++i){
		ans=min(ans,f[k-1][x1][y1][x2][i]+f[1][x1][i][x2][y2]);
		ans=min(ans,f[k-1][x1][i][x2][y2]+f[1][x1][y1][x2][i]);
	}
	return ans;
}
int main(){
	int n=read<int>();
	for(int i=1;i<=8;++i)for(int j=1;j<=8;++j)
		s[i][j]=read<int>()+s[i][j-1]+s[i-1][j]-s[i-1][j-1];
	for(int x1=0;x1<8;++x1)for(int y1=0;y1<8;++y1)
		for(int x2=x1+1;x2<=8;++x2)for(int y2=y1+1;y2<=8;++y2){
			int p=s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1];
			f[1][x1][y1][x2][y2]=p*p;
		}
	for(int k=2;k<=n;++k)
		for(int x1=0;x1<8;++x1)for(int y1=0;y1<8;++y1)
		for(int x2=x1+1;x2<=8;++x2)for(int y2=y1+1;y2<=8;++y2)
			f[k][x1][y1][x2][y2]=calc(k,x1,y1,x2,y2);
	printf("%.3lf
",sqrt((double)f[n][0][0][8][8]/n-(double)s[8][8]*s[8][8]/n/n));
	return 0;
}

POJ1390 Blocks

Language:Default

Blocks

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 6506		Accepted: 2689

Description

Some of you may have played a game called 'Blocks'. There are n blocks in a row, each box has a color. Here is an example: Gold, Silver, Silver, Silver, Silver, Bronze, Bronze, Bronze, Gold.
The corresponding picture will be as shown below:

Figure 1
If some adjacent boxes are all of the same color, and both the box to its left(if it exists) and its right(if it exists) are of some other color, we call it a 'box segment'. There are 4 box segments. That is: gold, silver, bronze, gold. There are 1, 4, 3, 1 box(es) in the segments respectively.

Every time, you can click a box, then the whole segment containing that box DISAPPEARS. If that segment is composed of k boxes, you will get k*k points. for example, if you click on a silver box, the silver segment disappears, you got 4*4=16 points.

Now let's look at the picture below:

Figure 2

The first one is OPTIMAL.

Find the highest score you can get, given an initial state of this game.

Input

The first line contains the number of tests t(1<=t<=15). Each case contains two lines. The first line contains an integer n(1<=n<=200), the number of boxes. The second line contains n integers, representing the colors of each box. The integers are in the range 1~n.

Output

For each test case, print the case number and the highest possible score.

Sample Input

2
9
1 2 2 2 2 3 3 3 1
1
1

Sample Output

Case 1: 29
Case 2: 1

Source

Liu Rujia@POJ

题目的方块可以表示成color[i], len[i], 1 <= i <= l,其中l表示有多少段不同的颜色方块。color[i]表示第i 段的颜色，len[i]表示第i 段的方块长度。

设dp[i, j, k]表示把(color[i], len[i]) , (color[i+1], len[i+1]), ……, (color[j], len[j] + k)合并的最大得分。

考虑(color[j], len[j] + k)这一段，

1. 马上消掉，dp[i, j-1, 0] + (len[j] + k) ^ 2;
2. 和前面的若干段一起消，可以假设这若干段中最后面得那一段是p，则此时的得分是dp[i, p, len[j]+k] + dp[p+1, j-1, 0].

于是有 dp[i, j, k] = max(f[i, j-1, 0] + (len[j] + k) ^ 2, dp[ i, p, len[j]+k ] + dp[p+1, j-1, 0]),其中color[p] == color[r];

#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=201;
int n,a[N],tot,id,c[N],cnt[N];
int o[N],nxt[N],x[N][N],f[N][N][N];
void Blocks(){
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	tot=0,memset(cnt,0,sizeof cnt);
	for(int t=1;t<=n;){
		c[++tot]=a[t];
		while(t<=n&&a[t]==c[tot])
			++cnt[tot],++t;
	}
	memset(o,0,sizeof o);
	for(int i=1;i<=tot;++i)
		nxt[i]=o[c[i]],o[c[i]]=i;
	memset(x,0,sizeof x);
	for(int i=tot;i;--i)
		for(int j=1;j<=n;++j) // suffix cnt
			x[j][i]=x[j][i+1]+(j==c[i]?cnt[i]:0);
	memset(f,0,sizeof f);
	for(int len=1;len<=tot;++len)
		for(int l=1;l+len-1<=tot;++l){
			int r=l+len-1;
			for(int i=0;i<=x[c[r]][r+1];++i){
				f[l][r][i]=f[l][r-1][0]+(cnt[r]+i)*(cnt[r]+i);
				for(int p=nxt[r];p>=l;p=nxt[p])
					f[l][r][i]=max(f[l][r][i],f[l][p][cnt[r]+i]+f[p+1][r-1][0]);
			}
		}
	printf("Case %d: %d
",++id,f[1][tot][0]);
}
int main(){
	for(int t=read<int>();t--;) Blocks();
	return 0;
}