poj3280
题意：
小写字母组成的长度为2000的字符串，每个字母的加入和删除都有代价，为通过插入或删除一定的字母使得原字符串成为回文串。为代价最少是多少？
简单的区间动规。
f[i][j]:字符串从第i个到第j个的字串成为回文串的最小代价
如果s[i]==s[j]，则f[i][j]=f[i+1][j];
如果s[i]!=s[j]，则要么删除s[i]或者在s[j]后面加上一个s[i],然后使得i+1到j之间回文，要么删掉s[j]或者在s[i]前加入一个s[j].然后使得i到j-1之间回文。
所以s[i][j]=minf(f[i][j-1]+del[j],f[i][j-1]+add[j],f[i+1][j]+del[i],f[i+1][j]+add[i])
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2010;
int f[maxn][maxn];
char s[maxn],c[3];
int n,m;
int g[30][2];
int minf(int a,int b,int c,int d)
{
return min(min(a,b),min(c,d));
}
int main()
{
scanf("%d%d",&m,&n);
scanf("%s",s+1);
for(int a,b,i=1;i<=m;++i)
{
scanf("%s%d%d",c,&a,&b);
g[c[0]-'a'][0]=a;g[c[0]-'a'][1]=b;
}
for(int i=n;i>0;--i)
for(int j=i;j<=n;++j)
if(i!=j)
{
if(s[i]==s[j])f[i][j]=f[i+1][j-1];
else f[i][j]=minf(f[i][j-1]+g[s[j]-'a'][0],f[i][j-1]+g[s[j]-'a'][1],f[i+1][j]+g[s[i]-'a'][0],f[i+1][j]+g[s[i]-'a'][1]);
}
cout<<f[1][n]<<endl;
return 0;
}
CF 254h
题意：
给定一个长度为n的字符串，有q次询问，每次询问求出l − r区间内回文的数量
数据范围：$1 < = n < = 5000 , 1 < = q < = 1 0^6 $
例如aba形成的回文有：a，b，a，aba四个回文串
f[i][j]：字符串i到j之间回文串的数量
那么里包含的分为4类
- 包含i,不含j,f[i][j-1]
- 包含j,不含i,f[i+1][j]
- 不包含i,j,f[i+1][j-1]
- 同时包含i,j,s[i][j]
根据容斥
f[i][j]=f[i][j-1]+f[i+1][j]-f[i+1][j-1]+(s[i][j]是回文）
#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
int f[maxn][maxn];
bool g[maxn][maxn];
char s[maxn];
int n,q;
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;++i)g[i+1][i]=1;
for(int i=n;i>0;--i)
for(int j=i;j<=n;++j)
if(i==j)g[i][j]=1;
else g[i][j]=(g[i+1][j-1]&&(s[i]==s[j]));
for(int i=n;i>0;--i)
for(int j=i;j<=n;++j)
if(i==j)f[i][j]=1;
else f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+g[i][j];
scanf("%d",&q);
for(int x,y,i=1;i<=q;++i)
{
scanf("%d%d",&x,&y);
printf("%d\n",f[x][y]);
}
return 0;
}
bzoj4922
题意：
现给定n个括号序列，你需要选择若干序列，将它们按一定的顺序从左往右拼接起来，得到一个合法的括号序列。求可以得到的合法的括号序列的长度的最大值。
数据范围：\(n \leq 300,字符串长度 \leq 300\)
贪心加动规
贪心原理与洛谷6927、4025类似。
动规，f[i][j]：前i个序列，有j个左括号未匹配的最大长度。
如果不选当前第i个序列，则f[i][j]=f[i-1][j]
如果选择了当前第i个序列，则f[i][j]=max(f[i][j],f[i-1][j-zuo[i]+you[i]]+chang[i]),条件为第i个序列的右括号不能多余前i-1个积累的左括号数。
#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
int n;
int f[maxn][maxn*maxn];
char s[maxn];
struct node
{
int a,b,w,bj;
}sz[maxn];
bool cmp(node x,node y)
{
if(x.bj!=y.bj)return x.bj<y.bj;
else
{
if(x.bj==0)return x.b<y.b;
else if(x.bj==1)return x.a<y.a||(x.a==y.a&&x.b-x.a>y.b-y.a);
else return x.a>y.a;
}
}
int main()
{
freopen("4922.in","r",stdin);
freopen("4922.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",s);
sz[i].w=strlen(s);
for(int j=0;j<sz[i].w;++j)
if(s[j]=='(')sz[i].b++;
else
{
if(sz[i].b)sz[i].b--;
else sz[i].a++;
}
if(sz[i].a==0&&sz[i].b!=0)sz[i].bj=0;
else if(sz[i].a&&sz[i].b)sz[i].bj=1;
else sz[i].bj=2;
}
sort(sz+1,sz+1+n,cmp);
int tj=0;
for(int i=1;i<=n;++i)
{
tj+=sz[i].b;
for(int j=0;j<=tj;++j)
{
f[i][j]=f[i-1][j];
if(j-sz[i].b>=0)f[i][j]=max(f[i][j],f[i-1][j-sz[i].b+sz[i].a]+sz[i].w);
}
}
cout<<f[n][0]<<endl;
return 0;
}
luogu4158 粉刷匠
[SCOI2009]粉刷匠
题目描述
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入格式
第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。
输出格式
包含一个整数，最多能正确粉刷的格子数。
样例 #1
样例输入 #1
3 6 3
111111
000000
001100
样例输出 #1
16
提示
30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
动规套动规
g[k][i][j]:第k块板的前i个格子刷j次能够得到的最大分数
\(g[i][i][j]=max(g[k][x][j-1]+max(hong(x+1,i),lan(x+1,i))),j-1 \leq x \leq i\)
f[i][j]:前i块板子刷j次最大能够得分是多少
\(f[i][j]=max(f[i-1][j-x]+g[i][m][x]),0 \leq x \leq min(m,j)\)
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int maxt=2505;
int n,m,t;
int f[maxn][maxn][maxn],ff[maxn][maxt];
char s[maxn];
int tj[maxn];
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;++i)
{
scanf("%s",s+1);
for(int j=1;j<=m;++j)tj[j]=tj[j-1]+(s[j]=='1');
for(int j=1;j<=m;++j)
for(int k=1;k<=j;++k)
for(int x=0;x<j;++x)
f[i][j][k]=max(f[i][j][k],f[i][x][k-1]+max(tj[j]-tj[x],(j-tj[j]-x+tj[x])));
}
for(int i=1;i<=n;++i)//注意内存循环两个min的应用
for(int j=1;j<=min(t,i*m);++j)
for(int x=1;x<=min(j,m);++x)
ff[i][j]=max(ff[i][j],ff[i-1][j-x]+f[i][m][x]);
cout<<ff[n][t]<<endl;
return 0;
}
luogu1044
题意：
没什么题意，就是求卡特兰数，当然可以用\(O(n^2)\)的方式求。但是也可以用\(O(n)\)的方法求。
卡特兰数的通项公式为\(C(2*n,n)/(n+1)\)
#include<bits/stdc++.h>
using namespace std;
int n;
long long c(int x,int y)
{
int q=1,h=x;
long long ans=1;
for(int i=1;i<=y;++i,q++,h--)ans=ans*h/q;
return ans;
}
int main()
{
cin>>n;
cout<<c(n+n,n)/(n+1)<<endl;
return 0;
}