POJ2342：
题意：某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。
题解：
当i来的时候，dp[i][1] += dp[j][0];//j为i的下属
当i不来的时候，dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
//#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define inf 10000000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//*************************************************************** int dp[][];
int vis[];
int parent[];
int n,a,b;
void sp(int x)
{
vis[x]=;
for(int i=;i<=n;i++)
{
if(parent[i]==x&&!vis[i])
{
sp(i);
dp[x][]+=max(dp[i][],dp[i][]);
dp[x][]+=dp[i][];
}
}
}
int main()
{ while(cin>>n)
{ memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
scanf("%d",&dp[i][]);
memset(vis,,sizeof(vis)); int root=;
memset(parent,,sizeof(parent));
while(scanf("%d%d",&a,&b)&&a&&b)
{
parent[a]=b;
root=b;
}
sp(root);
printf("%d\n",max(dp[root][],dp[root][]));
}
return ;
}
代码狗
vijos1642
题解：我们先依次求出每棵树的先根遍历序，并保存在同一个序列list[]中。 为了利用上面的结论，我们还要求出以节点i为根的子树的节点总数count[i]。
定义： v[i]表示第i个物品的权值 dp[i][j]表示从第i个物品到第n个物品，最多花费j，能得到的最大权值和。
状态转移： 对于一个节点，我们考虑是否购买它： 购买：那么我们继续考虑它后面的节点 不购买：那么我们跳过它的子孙节点
方程如下： F[i][j]=Max{F[i+1][j-cost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}
///
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
typedef long long ll;
using namespace std;
#define inf 10000000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//***************************************************************
///先根遍历序
int list[];
int s[],a[][];
int v[],counts[];
int dp[][];
int q;
int n,m;
int dfs(int k)
{
list[++q]=k;
if(s[k]==){return ++counts[k];}
for(int i=;i<=s[k];i++)
{
counts[k]+=dfs(a[k][i]);
}
return ++counts[k];
}
int main()
{
int t;
memset(dp,-,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{ scanf("%d%d",&v[i],&t);
while(t--)
{
scanf("%d",&a[i][++s[i]]);
}
}
dfs();
for(int i=;i<=n;i++){dp[i][]=;dp[i][]=v[list[i]];}
for(int i=n-;i>=;i--)
{
for(int j=;j<=m;j++)
{
dp[i][j]=max(dp[i+][j-]+v[list[i]],dp[i+counts[list[i]]][j]);
}
}
int ans=-inf;
for(int i=;i<=m;i++)
ans=max(dp[][i],ans);
printf("%d\n",max(ans,));
return ;
}
代码狗
POJ 1947
题解：dp[root][i]表示以root为根得到节点数为i 所需要删除的少边数
转移：
dp[root][i]=dp[root][i]+1; 不加某son，边+1；
dp[root][i]=min(dp[root][i-j]+dp[son][j]);加某son，j代表son为根的树节点数
最后注意：非根节点边数+1；因为要删除与父亲节点的边
///
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
typedef long long ll;
using namespace std;
#define inf 10000000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//***************************************************************
int dp[][];
vector<int >son[];
int dfs(int root,int pre)
{
dp[root][]=;
int sum=;
for(int i=;i<son[root].size();i++)
{
int s=son[root][i];
if(s==pre)continue;
sum+=dfs(s,root);
for(int k=sum;k>=;k--)
{
dp[root][k]=dp[root][k]+;
for(int h=;h<k;h++)
{
dp[root][k]=min(dp[root][k],dp[root][k-h]+dp[s][h]);
}
}
}
return sum;
}
int main()
{
int n,m,a,b;
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&m);
// for(int i=1;i<=n;i++)dp[i][0]=1;
for(int i=;i<n;i++)
{
scanf("%d%d",&a,&b);
son[a].push_back(b);
son[b].push_back(a);
}
dfs(,-);
int ans=dp[][m];
for(int i=;i<=n;i++){
if(dp[i][m]+<ans)ans=dp[i][m]+;
}
printf("%d\n",ans);
return ;
}
代码
HDU 1011 Starship Troopers
转移：dp[i][k] = max(dp[i][k], dp[i][k-l] + dp[i][l]);
//зїеп:1085422276
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
#define inf 100000000
using namespace std; inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//***************************************
int v[];
int cost[];
int dp[][];
vector<int >tr[];
int n,m;
void dfs(int k,int pre)
{
for(int i=cost[k];i<=m;i++)
dp[k][i]=v[k];
for(int i=;i<tr[k].size();i++){
if(pre==tr[k][i])continue;
dfs(tr[k][i],k);
int son=tr[k][i];
for(int j=m;j>=cost[k];j--)
{
for(int l=;l+cost[k]<=j;l++)
{
dp[k][j]=max(dp[k][j],dp[son][l]+dp[k][j-l]);
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==-&&m==-)break;
// init();
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
scanf("%d%d",&cost[i],&v[i]);
cost[i]=cost[i]/+(cost[i]%!=);
// if(cost[i]%20!=0)cost[i]+=1;
tr[i].clear();
}
int a,b;
for(int i=;i<n;i++)
{
scanf("%d%d",&a,&b);
tr[a].push_back(b);
tr[b].push_back(a);
}
if(m==){printf("0\n");continue;}
dfs(,-);
printf("%d\n",dp[][m]);
}
return ;
}
代码
CodeForces 161D Distance in Tree
题目链接：http://codeforces.com/contest/161/problem/D
简单树形dp：维护各个节点1到k的情况就可以了；
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//**************************************************************************************
ll ans,dp[][];///以i为节点构成路径长度为j的种类树；
vector<int >G[];
int fa[];
int vis[];
int n,m;
void dfs(int k)
{
dp[k][]=;
for(int i=;i<G[k].size();i++){
int son=G[k][i];
if(vis[son])continue;
vis[son]=;
dfs(son);
for(int j=;j<m;j++){
ans+=dp[k][m-j-]*dp[son][j];
}
for(int i=;i<=m;i++)
{
dp[k][i]+=dp[son][i-];
}
}
} int main()
{ scanf("%d%d",&n,&m);
int a,b;
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
memset(vis,,sizeof(vis));
memset(dp,,sizeof(dp));
vis[]=;
dfs(); cout<<ans<<endl;
return ;
}
代码
【tyvj1520】树的直径
题目链接：http://www.tyvj.cn/p/1520
dp1[]，dp2[]分别代表从当前根节点出发所能到达的最长链与次长链，感谢HZWER指点；。。。。。
///
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
typedef long long ll;
using namespace std;
#define inf 10000000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//*************************************************************** struct ss
{
int to,next,v;
}e[*];
int head[],t,dp1[],dp2[],ans;
void add(int u,int v,int w)
{
e[t].to=v;
e[t].next=head[u];
e[t].v=w;
head[u]=t++;
}
void dp(int x,int pre)
{
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==pre)continue;
dp(e[i].to,x);
if(dp1[e[i].to]+e[i].v>dp1[x])
{
dp2[x]=dp1[x];
dp1[x]=dp1[e[i].to]+e[i].v;
}
else dp2[x]=max(dp1[e[i].to]+e[i].v,dp2[x]);
}
ans=max(dp1[x]+dp2[x],ans);
}
int main()
{int n;
memset(head,,sizeof(head));
t=;
ans=;
int u,v,w;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dp(,);
cout<<ans<<endl; return ;
}
代码