感覺都是基本的DP，除了charrec不好寫罷了。
theme：求出差序列，然后求自身不同的最長公共子串。注意是不同的。
milk4：現(xiàn)ID-DFS枚舉方案然后完全背包判定，我常數(shù)小直接過了，有TLE可以改記憶化搜索判定。
bigbrn：最大可行正方形，太基礎(chǔ)了，連預(yù)處理都省了。。。。。
tour：兩條線的DP，頭腦發(fā)熱要上SPFA的模板，讓后仔細(xì)看了數(shù)據(jù)，三重循環(huán)結(jié)束。
charrec：很有價(jià)值，一般人看著就覺的太難了，然后仔細(xì)讀完題想想就是DP，但確實(shí)不好寫。
twofive:感覺最有價(jià)值的一道，首先它是一道構(gòu)造/統(tǒng)計(jì)類的DP，然后又是五維DP，各種邊界。顯然有記憶化搜索比較賺。
最有價(jià)值的一題
/**//*
USER:zyn19961
TASK:twofive
LANG:C++
*/
#include<string>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
//
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define DFOR(i,r,l) for (int i=(r);i>=(l);i--)
//
#define MP make_pair
#define FT first
#define SD second
//
typedef long long Int64;
const int INF=~0U>>2;
const int maxn=10;
//
ifstream fin("twofive.in");
ofstream fout("twofive.out");
int F[maxn][maxn][maxn][maxn][maxn];
bool used[maxn*maxn];
int mx[maxn],my[maxn];
int count(int a,int b,int c,int d,int e,int now);
void work1();//n
void work2();//w
//
int main()
{
char c;fin>>c;
if(c=='N')work1();
else work2();
fin.close();
fout.close();
return 0;
}
int count(int a,int b,int c,int d,int e,int now){
int &t=F[a][b][c][d][e];
if(t)return t;
if(used[now])return t=count(a,b,c,d,e,now+1);//
if(a<5&&mx[0]<now&&my[a]<now)t+=count(a+1,b,c,d,e,now+1);
if(b<a&&mx[1]<now&&my[b]<now)t+=count(a,b+1,c,d,e,now+1);
if(c<b&&mx[2]<now&&my[c]<now)t+=count(a,b,c+1,d,e,now+1);
if(d<c&&mx[3]<now&&my[d]<now)t+=count(a,b,c,d+1,e,now+1);
if(e<d&&mx[4]<now&&my[e]<now)t+=count(a,b,c,d,e+1,now+1);
return t;
}
void work1(){
int sum;fin>>sum;
int line[maxn];
string s;
MM(mx,0xff),MM(my,0xff),MM(used,false),MM(line,0);
FOR(i,0,24){
line[i/5]++;
int j;
for(j=0;j<=24;j++)
if(!used[j]&&mx[i/5]<j&&my[i%5]<j){
used[j]=true;
mx[i/5]=my[i%5]=j;
MM(F,0);
F[5][5][5][5][5]=1;
int t=count(line[0],line[1],line[2],line[3],line[4],0);
if(sum-t<=0)break;
else sum-=t;
used[j]=false;
}
s+=char(j+'A');
}
fout<<s<<"\n";
}
void work2(){
string s;fin>>s;
int sum=0;
int line[maxn];
MM(line,0),MM(mx,0),MM(my,0),MM(used,false);
FOR(i,0,24){
line[i/5]++;
int j;
for(j=0;j<=s[i]-'A'-1;j++)
if(!used[j]&&mx[i/5]<j&&my[i%5]<j){
mx[i/5]=my[i%5]=j;
MM(F,0);
F[5][5][5][5][5]=1;
used[j]=true;
sum+=count(line[0],line[1],line[2],line[3],line[4],0);
used[j]=false;
}
used[j]=true;
mx[i/5]=my[i%5]=j;
}
fout<<sum+1<<"\n";
}
接著看了一下Chapter 6的rectbarn
顧名思義，就是求最大子矩形，顯然也是DP。
N久以前看過一篇集訓(xùn)隊(duì)論文，然后就按照上面的一種方法A掉了這題。
（上面講了兩種方法，我顯然寫的是最水的N^2的算法）
惡搞了一下代碼：
見不得人的代碼
/**//*
USER:zyn19961
TASK:rectbarn
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
//
#define MM(a,i) memset((a),i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define DFOR(i,r,l) for (int i=(r);i>=(l);i--)
#define NFOR(i,l,r) for (i=(l);i<=(r);i++)
#define NDFOR(i,r,l) for (i=(r);i>=(l);i--)
#define PFOR(p,a,next) for(int p=a;p;p=next[p])
#define NPFOR(p,a,next) for(p=a;p;p=next[p])
//
typedef long long int64;
const int INF=~0U>>2;
const int maxn=3001;
//
ifstream fin("rectbarn.in");
ofstream fout("rectbarn.out");
//
bool xx[maxn][maxn];
int F[2][maxn],L[2][maxn],R[2][maxn],Left[maxn],Right[maxn];
int main(){
int r,c,p;
int x,y;
int ans=0,now=0,last=1;
MM(xx,true);
fin>>r>>c>>p;
if(!p){fout<<r*c<<"\n";return 0;}
FOR(i,1,p)fin>>x>>y,xx[y][x]=false;
FOR(i,1,c){
now^=1,last^=1;
Left[0]=0,Right[r+1]=0;
FOR(j,1,r)xx[i][j]?Left[j]=Left[j-1]+1:Left[j]=0;
DFOR(j,r,1)xx[i][j]?Right[j]=Right[j+1]+1:Right[j]=0;
FOR(j,1,r)xx[i][j]? (F[now][j]=F[last][j]+1,
L[now][j]=min(L[last][j],Left[j]),
R[now][j]=min(R[last][j],Right[j]))
:(F[now][j]=0,L[now][j]=INF,R[now][j]=INF);
FOR(j,1,r)ans=max(ans,F[now][j]*(L[now][j]+R[now][j]-1));
}
fout<<ans<<"\n";
fin.close();
fout.close();
return 0;
}