51 Nod 1021 石子归并
模板题，敲就完事了，注意一下这种状态转移方程有个四边形的优化（时间）
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std; int n;
const int maxn=1e3+;
int f[maxn][maxn], s[maxn][maxn], a[maxn], sum[maxn]; void solve_sim()
{
memset(f, 0x3f, sizeof(f));
for(int i=; i<=n; i++)
f[i][i]=; for(int len=; len<n; len++)
for(int i=; i<=n-len; i++)
{
int j=i+len;
for(int k=i; k<j; k++)
f[i][j]=min(f[i][j], f[i][k]+f[k+][j]+sum[j]-sum[i-]);
}
} void solve_opt()
{
memset(f, 0x3f, sizeof(f));
for(int i=; i<=n; i++){
f[i][i]=; s[i][i]=i;
} for(int len=; len<n; len++)
for(int i=; i<=n-len; i++)
{
int j=i+len;
for(int k=s[i][j-]; k<=s[i+][j]; k++)
{
if(f[i][j]>f[i][k]+f[k+][j])
{
f[i][j]=f[i][k]+f[k+][j];
s[i][j]=k;
}
}
f[i][j]+=sum[j]-sum[i-];
}
} int main()
{
cin>>n;
for(int i=; i<=n; i++)
{
cin>>a[i];
sum[i]=sum[i-]+a[i];
} solve_sim();
solve_opt(); cout<<f[][n]<<endl;
return ;
}
POJ 3186 喂牛
题意：给你n个数字.....每次你可以取出最左端的数字或者取出最右端的数字，一共取n次取完。假设你第i次取的数字是x，你可以获得i*x的价值。求总价值之和最大。
题解：区间DP问题，子问题：在dp[i][j]这段区间所获得的最大价值；
划分：取左边或者取右边，这个是从底往上推的，初始化要注意，
方程：f[i][j]=max(f[i+1][j]+(n-len)*a[i], f[i][j-1]+(n-len)*a[j])
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF=0x3f3f3f3f;
const int maxn=2e3+;
int f[maxn][maxn], a[maxn]; int main()
{
//freopen("in.txt", "r", stdin);
int n; cin>>n;
for(int i=; i<=n; i++){
cin>>a[i];
f[i][i]=a[i]*n;
}
for(int len=; len<n; len++)
for(int i=; i<=n-len; i++){
int j=i+len;
f[i][j]=max(f[i+][j]+(n-len)*a[i], f[i][j-]+(n-len)*a[j]);
}
cout<<f[][n]<<endl;
return ;
}
POJ 2955 括号匹配
题意：给一串字符，求可以匹配的括号个数，有(), [],这2种括号
题解：区间DP问题，子问题：在区间i，j上的最大可匹配的括号数目；
划分：首尾匹配， 首尾不匹配，当首尾不匹配的时候必然可以由2段区间合并来（想一下），枚举所有的子区间组合（分割点）；
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std; const int maxn=;
char s[maxn];
int f[maxn][maxn]; int main()
{
while(scanf("%s",s+), s[]!='e')
{
memset(f, , sizeof(f));
int n=strlen(s+);
for(int len=; len<n; len++)
for(int i=; i<=n-len; i++) //注意这个i是可以等于n-len
{
int j=i+len;
if(s[i]=='('&&s[j]==')' || s[i]=='['&&s[j]==']')
f[i][j]=f[i+][j-]+; //不是由拼接得来的
for(int k=i; k<j; k++)
f[i][j]=max(f[i][j], f[i][k]+f[k+][j]);//由拼接得来的
}
printf("%d\n", f[][n]);
}
return ;
}
POJ 3280 求变成回文串的代价
题意：给定一个字符串S，字符串S的长度为M，字符串S所含有的字符的种类的数量为N（最多26种 小写字母），然后给定这N种字符Add与Delete的代价，求将S变为回文串的最小代价和。
题解：区间DP，子问题：当i，j的区间是回文串的时候所要付出的代价；
划分：首尾相等，直接转， 首尾不等，长区间是由比它短一的区间延展来的，从左边还是右边
注意：这个初始化，我是真的有点问题，找for循环下的状态转移的临界条件，如果不行的话，在for循环下初始化；
这个给出2个cost，删除和添加其实只要选其中较小的一个即可；
总结：此题在写的时候，思路就错了，这个区间dp问题，它的问题不是由2段短的区间和并来的， 而是由短区间往2边扩展来的，直到扩展到1-n；
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string >
using namespace std; const int maxm=2e3+;
const int INF=0x3f3f3f3f;
int cost[], f[maxm][maxm];
char s[maxm]; int main()
{
//freopen("in.txt", "r", stdin);
int k,n; cin>>k>>n;
scanf("%s", s+);
while(k--)
{
char data; cin>>data;
int ac,dc; cin>>ac>>dc;
cost[data-'a']=min(ac, dc);
} /*
memset(f, 0x3f, sizeof(f));
for(int i=0; i<=n; i++) f[i][i]=0; ///这个初始化是不对的，找了我好久
*/ for(int len=; len<n; len++)
for(int i=; i<=n-len; i++)
{
int j=i+len;
f[i][j]=INF;
if(s[i]==s[j])
f[i][j]=f[i+][j-];
else
{
f[i][j]=min(f[i][j], f[i+][j]+cost[s[i]-'a']);
f[i][j]=min(f[i][j], f[i][j-]+cost[s[j]-'a']);
}
}
cout<<f[][n]<<endl;
return ;
}