D - Tree of Tree ZOJ - 3201

这个题目我开始是这么定义的dp[i][j][0] dp[i][j][1] 表示对于第i个节点还有j个的选择 0 代表不选这个节点，1 代表选这个节点。

然后我写了，对题目理解出现了偏差写出来一个错误的，然后正确理解题意发现这样子写好麻烦。转移方程很难写。

上网搜题解，网上基本上都是这么定义的 dp[i][j]表示选第 i 个节点该子树的节点数为  j  的最大带权值。

所以这个就可以变成一个树形dp+01背包。

这个状态转移方程应该就是 dp[u][j]=max(dp[u][j] ，dp[u][j-k]+dp[v][k])  其实我觉得这个转移方程也没有那么好想。

这个01背包就是在枚举以u为根节点的这棵树的每一颗子树取多少个节点。

#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
int dp[][];
vectorG[];
int n, k;

void dfs(int u,int pre)
{
for (int i = ; i < G[u].size(); i++) { int v = G[u][i]; if (v == pre) continue; dfs(v, u); for (int j = k; j >= ; j--)
{
for (int h = ; h < j; h++)
{
dp[u][j] = max(dp[u][j], dp[u][j - h] + dp[v][h]);
}
}
}
}

int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp, , sizeof(dp));
for (int i = ; i <= n; i++) G[i].clear();
for (int i = ; i < n; i++) {
scanf("%d", &dp[i][]);
}
for(int i=;i<n;i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, -);
int ans = ;
for(int i=;i<n;i++)
{
ans = max(ans, dp[i][k]);
}
printf("%d\n", ans);
}
return ;
}

树形dp

C - Brackets POJ - 2955

这个题目其实我觉得很像就是在求回文，所以和那个兔子的题目很像，但是呢，还是有一点点的不同

回忆一下兔子的题目  兔子传送门

这个题目的状态转移方程也就是

if(条件判断) dp[i][j]=max(dp[i+1][dp[j-1]+2,dp[i][j])

else dp[i][j]=max(dp[i+1][j],dp[i][j-1])

这个题目还有一个地方，就是因为我们定义的dp[i][j]表示从i到j的最大的匹配了的数量，所以呢，()()()

这种情况，如果你值是进行状态转移，那就会出现问题了，

因为dp[1][2]=2 dp[2][3]=1 dp[3][4]=2  所以 dp[1][4]=dp[2][3]+2这个就不对了，这个时候，我们应该找一个切断点。

dp[1][4]的切断点就是dp[1][2]+dp[3][4]=4

所以说还有有一个for循环来找这个断点，这个我也没想明白是看题解的。

#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
int dp[][];
char s[];

int main()
{
while(scanf("%s",s+)!=EOF)
{
if (s[] == 'e') break;
memset(dp, , sizeof(dp));
int len = strlen(s + );
int ans = ;
for(int i=;i<=len;i++)
{
for(int j=;j+i-<=len;j++)
{
int ends = i + j - ;
if ((s[j]=='('&&s[ends]==')')||(s[j]=='['&&s[ends]==']')) dp[j][ends] =dp[j + ][ends - ] + ;
else dp[j][ends] = max(dp[j + ][ends], dp[j][ends - ]);
for (int k = j; k < ends; k++) dp[j][ends] = max(dp[j][ends], dp[j][k] + dp[k+][ends]);
//printf("j %c ends %c dp[%d][%d]=%d\n", s[j],s[ends],j, ends, dp[j][ends]);
}
}
printf("%d\n", dp[][len]);
}
return ;
}

区间dp

Q - 最大报销额HDU - 1864

这个题目我感觉还比较简单啊，就是字符串处理要注意一下，可以看我的另外一篇博客用sscanf的方法来处理很方便。

https://www.cnblogs.com/EchoZQN/p/10830015.html

处理完之后就是一个简单的01背包，需要注意的是因为有小数，所以*100转化成整数来处理即可。

#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 3e6 + ;
int dp[maxn], n, m;
int a[];
double q;

int main()
{
while(scanf("%lf%d",&q,&m)!=EOF)
{
if (m == ) break;
n = (int)(q * );
int tot = ;
for(int k=;k<=m;k++) { int num; scanf("%d", &num); char ch, cs[]; double mon; int A = , B = , C = , flag = ; for(int i=;i<=num;i++) { scanf("%s", cs); sscanf(cs, "%c:%lf", &ch, &mon); int mm = (int)(mon * ); if (ch == 'A') A += mm; else if (ch == 'B') B += mm; else if (ch == 'C') C += mm; else flag = ; if (A > || B > || C > || (A + B + C) > ) flag = ;
// printf("%d %d %d\n", A, B, C);
}
if (flag == ) a[++tot] = A + B + C;
}
memset(dp, -inf, sizeof(dp));
dp[] = ;
//for (int i = 1; i <= tot; i++) printf("%d\n", a[i]); //printf("n=%d\n", n); for(int i=;i<=tot;i++) { for(int j=n;j>=a[i];j--)
{
dp[j] = max(dp[j], dp[j - a[i]]);
}
}
//printf("%d\n", dp[n]);
int ans = ;
for(int i=n;i>=;i--)
{
if(dp[i]>=)
{
ans = i;
break;
}
}
printf("%.2lf\n", ans*1.0 / );
}
return ;
}

01背包

这个就是今天的dp训练了，接下来就是复习以前的算法。