哇!简直恶心的递推，生推了半天。。感觉题不难，但是恶心，不推出来又难受。。一不小心还A了[]~(￣▽￣)~*，AC的猝不及防。。。
先递推求出f[i][1](1<=i<=n-1),f[n][i](2<=i<=n)和f[i][j](2<=i<=n-1,1<=j<=i)，再递推一次求f[1][j](2<=j<=n),f[1][n]即为答案。其实不太肯定这样是否一定正确，因为我没有特别考虑j=0的边界情况，感觉好像也用不到这个情况。而且要用long long，刚开始用int会WA。
Reference Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll f[][]={}; int main()
{
int n,an1;
while(scanf("%d%d",&n,&an1)==)
{
memset(f,,sizeof(f));
f[n][]=an1;
for (int i=n-;i>=;i--){
f[i][]=f[i+][]*;
}
for(int i=;i<=n;i++){
f[n][i]=f[n][i-]*;
}
for(int i=n-;i>=;i--){
for(int j=;j<=i;j++){
for(int k1=i+;k1<=n;k1++){
f[i][j]=max(f[i][j],f[k1][]+f[k1][j]);
}
ll t=;
for(int k2=;k2<j;k2++){
t=max(t,f[i][k2]+f[n][k2]);
}
f[i][j]+=t;
}
}
for(int j=;j<=n;j++){
for(int k=;k<j;k++){
f[][j]=max(f[][j],f[][k]+f[k+][j]);
}
}
cout<<f[][n]<<endl;
}
return ;
}
UVa 10520 递推
后来又看到了有人用深搜写，感觉其实好理解点而且不用想他们之间的递推关系，按照要求往下搜就好，省点脑子，比赛的时候适合这种写法。
Reference Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll f[][]={};
ll n,a; ll calc(int i,int j)
{
if(f[i][j]!=-)
return f[i][j];
if(i<j){
ll Max=;
for(int k=i;k<j;k++){
ll tmp=calc(i,k)+calc(k+,j);
Max=max(Max,tmp);
}
return f[i][j]=Max;
}
ll Max1=,Max2=;
if(i<n){
for(int k=i+;k<=n;k++){
ll tmp=calc(k,)+calc(k,j);
Max1=max(Max1,tmp);
}
}
if(j>){
for(int k=;k<j;k++){
ll tmp=calc(i,k)+calc(n,k);
Max2=max(Max2,tmp);
}
}
return f[i][j]=Max1+Max2;
}
int main()
{
while(cin>>n>>a)
{
memset(f,-,sizeof(f));
f[n][]=a;
f[][n]=calc(,n);
cout<<f[][n]<<endl;
}
return ;
}
UVa 10520 深搜