DP练习2-0313（VJ）
比赛地址
T1（Brackets）
区间DP
先枚举断点，如果 \(l\) 和 \(r\) 括号匹配，那就和 \(f[l+1][r-1]\) 取 \(max\) 。
${\color{skyblue}{Code}}$
#include
#include
#include
#include
using namespace std;
const int N=105;
int f[N][N];
int main(){
string s;
while(cin>>s && s!="end"){
memset(f,0,sizeof f);
int le=s.size();
for(int len=1;len<=le;++len){
for(int l=0;l<=le-len;++l){
int r=l+len-1;
if(l==r) continue;
for(int j=l;j T2（Traveling by Stagecoach）
状压DP
压缩车票的状态。令 \(f[k][i]\) 表示从起点到第 \(i\) 个点时，车票状态为 \(k\) 时需要的最小时间。
每个点去找与它相连的点来更新当前的点。如果当前状态下 \(q\) 这张车票被用了，那就可以使其作为这两个点中使用的。
${\color{skyblue}{Code}}$
#include
#include
#include
#include
#include
using namespace std;
const int N=(1<<8)+5,INF=0x3f3f3f3f;
double f[35][N];
int n,m,p,a,b;
int v[10],ed[35][35];
void dp(){
for(int i=1;i<=m;++i)
for(int j=0;j<(1<>q)&1)
f[i][k]=min(f[i][k],f[j][k^(1<>n>>m>>p>>a>>b && n){
memset(ed,-1,sizeof ed);
for(int i=1;i<=n;++i) cin>>v[i];
for(int i=1;i<=p;++i){
int u,v,z;
cin>>u>>v>>z;
ed[u][v]=ed[v][u]=z;
}
dp();
double ans=INF;
for(int i=0;i<(1< T3（World Eater Brothers）
树形DP（参考这篇）
题意：一颗树但边有向，求让这颗树入度为 0 的点个数最多 2 个需要改变方向的边的数量。
令 \(f[x][i][j](j=0/1)\) 表示 \(x\) 这个点及其子树中有 \(i\) 个点入度为 0 时且 \(x\) 这个点入度是否为 0 （1：是，0：否）。
枚举每个子树 \(y\) ，再枚举已合并的和子树的入度为 0 的点的个数，同时枚举 \(x\) ，\(y\) 入度分别是否为 0。
${\color{skyblue}{Code}}$
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N=3e3+5;
int n;
int h[N],val[N*2],ver[N*2],nxt[N*2],co;
int f[N][5][2];
void add(int x,int y,int z){
val[++co]=z,ver[co]=y,nxt[co]=h[x],h[x]=co;
}
void dp(int x,int fa){
f[x][1][1]=0;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i],v=val[i];
if(y==fa) continue;
dp(y,x);
int g[5][2];memset(g,INF,sizeof g);
for(int j1=0;j1<3;++j1)
for(int j2=0;j2<3;++j2)
for(int kx=0;kx<2;++kx)
for(int ky=0;ky<2;++ky){
g[j1+j2][kx]=min(g[j1+j2][kx],f[y][j2+ky][ky]+f[x][j1][kx]+v);
\\x-->y
g[j1+j2][0]=min(g[j1+j2][0],f[y][j2][ky]+f[x][j1+kx][kx]+(v^1));
\\y-->x
}
memcpy(f[x],g,sizeof g);
}
}
int main(){
cin>>n;
for(int i=1;i>x>>y;
add(x,y,0),add(y,x,1);
}
memset(f,INF,sizeof f);
dp(1,0);
int ans=INF;
for(int i=0;i<3;++i)
ans=min(ans,min(f[1][i][0],f[1][i][1]));
cout< T4（Coloring Brackets）
题解都是用区间DP做的，但是也用了DFS。
可以把括号序列转化为一颗树，一对括号中的每一对括号是它的儿子节点。
这样就可以用树形DP做了。\(f[x][i][j]\) 表示 \(x\) 这个点包含的区间以 \(i\) 这个颜色开始，\(j\) 这个颜色结尾的方案数。
中间的转移有点烦要挨个枚举情况。记得取余和开 \(longlong\) 。
${\color{skyblue}{Code}}$
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int p=1e9+7;
int b[705],l[705],r[705],fa[705];
int cnt;
int ff[705][3][3];
vector son[705];
void dp(int x){
int tmp[3][3]={0};
for(int i=0;i>s;
int f=0;stack x;
for(int i=0;i