fwdiary(8) 区间dp，树形dp 记忆化搜索
1.划分大理石（背包问题）
多重背包问题，本题数据用二进制优化即可。
从6种大理石，每种有ai个，恰好选出重量为j，最终答案是 重量为总重/2
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 60010;
bool f[N];
int a[10];
int main()
{
while(true)
{
int m = 0;
for (int i = 1; i <= 6; i ++ )
{
cin >> a[i];
m += a[i] * i;
}
if(!m) break;
if(m&1) puts("Can't");
else
{
m/=2;
memset(f,0,sizeof f);
f[0]=true;
for(int i=1;i<=6;i++)
{
int s=a[i],k=1;
while(s>=k)
{
for(int j=m;j>=i*k;j--) f[j]|=f[j-i*k];
s-=k;
k*=2;
}
if(s) for(int j=m;j>=i*s;j--) f[j]|=f[j-i*s];
}
if(f[m]) puts("Can");
else puts("Can't");
}
}
return 0;
}2.棋盘分割
321. 棋盘分割 - AcWing题库
状态表示显然为，一个矩形区域四个坐标，加切割成多少块。
枚举一次切割的位置即可。注意切割之后，还有两种情况。假设切割成A，B两部分，一种是把A作为单独切出来的一块，然后继续切割B。另一种反之。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N =15,M=9;
const double INF=1e9;
double X;
int n,m=8;
int s[M][M];
double f[M][M][M][M][M];
int get_sum(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
double get(int x1,int y1,int x2,int y2)
{
double sum=get_sum(x1,y1,x2,y2)-X;
return sum*sum/n;
}
double dp(int x1,int y1,int x2,int y2,int k)
{
double &v=f[x1][y1][x2][y2][k];
if(v>0) return v;
if(k==1) return get(x1,y1,x2,y2);
v=INF;
for(int i=x1;i<x2;i++)
{
v=min(dp(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2),v);
v=min(dp(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2),v);
}
for(int i=y1;i<y2;i++)
{
v=min(v,get(x1,y1,x2,i)+dp(x1,i+1,x2,y2,k-1));
v=min(v,get(x1,i+1,x2,y2)+dp(x1,y1,x2,i,k-1));
}
return v;
}
int main()
{
cin>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
X=(double)s[m][m]/n;
memset(f,-1,sizeof f);
printf("%.3lf\n",sqrt(dp(1,1,m,m,n)));
return 0;
}3.消木块 区间dp，，多加一维
322. 消木块 - AcWing题库
如果只有l，r。那么再r之后，在l之前同时消去的方案可能记录不到，写不出状态转移方程。
因此先考虑多加一维，在r之后还连续消掉了co个块。
因此状态划分枚举在l，r内，如果wk==wr，则把k+1到r的消去，wk接上r之后的co个一起消去
枚举初值是把r消去，也就是l到r-1消去，再加（1+co）平方
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =210;
int f[N][N][N];
int n;
int a[N];
int dp(int l,int r,int co)
{
int &v=f[l][r][co];
if(v>=0) return v;
if(l>r) return 0;
v=dp(l,r-1,0)+(1+co)*(1+co);
for(int k=l;k<r;k++)
{
if(a[k]==a[r])
{
v=max(v,dp(l,k,1+co)+dp(k+1,r-1,0));
}
}
return v;
}
int main()
{
int T;
cin>>T;
for(int cases=1;cases<=T;cases++)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,-1,sizeof f);
printf("Case %d: %d\n",cases,dp(1,n,0));
}
}4.贿赂FIPA （树形dp+背包问题+记忆化搜索）
324. 贿赂FIPA - AcWing题库
选一个根节点就把整个子树都选了。那就状态表示，在以u为根的子树中选择，得到超过j张票的最小花费。
那么必要的信息就要子树中包含节点的个数。假设我们已经知道了这个size数组，来思考状态转移方程。首先遍历节点u的所有节点，枚举在该节点获得多少张票。此时我们应该知道，以子节点为根的子树中，选择k张票的最小代价，将这些看做物品（在子节点为根的子树中选择0到size(j)张票），那么实际上是个01背包问题
因此可解。最后不要忘记选择u本身的答案。
#include<iostream>
#include<algorithm>
#include<cstring>
#include <bits/stdc++.h>
using namespace std;
//以u为根的子树，获得j票的最小花费
const int N=210,M=2*N;
string s, a, b;
stringstream ss;
int n, m;
int val[N];
map<string, int> mp;int cnt;
int father[N];
int h[N], e[M], ne[M], idx;
int f[N][N], sz[N];
int fd(string s)
{
return mp.find(s) == mp.end() ? mp[s] = ++ cnt : mp[s];
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dp(int u)
{
f[u][0]=0;
sz[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father[u]) continue;
dp(j);
sz[u]+=sz[j];
}
for(int i=h[u];~i;i=ne[i])//从子树中选择
{
int ver=e[i];
if (ver == father[u]) continue;
for(int j=sz[u];j;j--)
{
for(int k=sz[ver];k;k--)
if(j>=k)
f[u][j]=min(f[u][j],f[u][j-k]+f[ver][k]);
}
}
if(u)//选择自身
for (int i = 1; i <= sz[u]; i ++ ) f[u][i] = min(f[u][i], val[u]);
}
int main()
{
while (getline(cin, s) && s[0] != '#')
{
cnt=0;
mp.clear(), cnt = idx = 0;
memset(h, -1, sizeof h);
memset(father, 0, sizeof father);
memset(f, 0x3f, sizeof f);
ss.clear(), ss.str(s); ss >> n >> m;
for (int i = 1, u, v; i <= n; i ++ )
{
getline(cin, s);
ss.clear(), ss.str(s); ss >> a;
u = fd(a), ss >> val[u];
while (ss >> b)
{
v = fd(b);
add(u, v), add(v, u);
father[v] = u;
}
}
for (int i = 1; i <= n; i ++ )
if (father[i] == 0)
add(i, 0), add(0, i);
dp(0);
printf("%d\n", f[0][m]);
}
}
5.计算机（树形dp 树的中心）
325. 计算机 - AcWing题库
某一点距离该点最远距离，就是往下最深距离，和网上最深距离中更深的一个；
往下最深距离简单，不说了、
往上最深距离就是：如果当前节点不是根节点往下d1所在分支，那么就是max(up[u],d1[u])
如果是，就是和d1[u]取最大值。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =10010,M=2*N;
const int INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int d1[N],d2[N],up[N];
int p[N];
bool isleaf[N];
int res[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dfs_d(int u,int father)
{
d1[u]=d2[u]=-INF;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father) continue;
int d=dfs_d(j,u)+w[i];
if(d>=d1[u])
{
d2[u]=d1[u];
d1[u]=d;
p[u]=j;
}
else if(d>d2[u]) d2[u]=d;
}
if(d1[u]==-INF)
{
d1[u]=d2[u]=0;
isleaf[u]=true;
}
return d1[u];
}
void dfs_u(int u,int father)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father) continue;
if(p[u]==j) up[j]=max(up[u],d2[u])+w[i];
else up[j]=max(up[u],d1[u])+w[i];
dfs_u(j,u);
}
}
void solve(int n)
{
memset(h,-1,sizeof h);
idx=0;memset(isleaf,0,sizeof isleaf);
for(int i=2;i<=n;i++)
{
int a,c;
cin>>a>>c;
add(a,i,c),add(i,a,c);
}
dfs_d(1,-1);
dfs_u(1,-1);
for(int i=1;i<=n;i++)
{
if(isleaf[i]) res[i]=up[i];
else res[i]=max(up[i],d1[i]);
cout<<res[i]<<endl;
}
}
int main()
{int n;
while(cin>>n)
{
solve(n);
}
}