奋战杭电ACM(DAY9)1011

发布时间:2016-12-7 1:50:34 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"奋战杭电ACM(DAY9)1011",主要涉及到奋战杭电ACM(DAY9)1011方面的内容,对于奋战杭电ACM(DAY9)1011感兴趣的同学可以参考一下。

开学了,用电脑时间越来越少,军校一大麻烦,班长还特别贱,心情极度不好。直接发题,尽量写注释。 Starship Troopers #include<iostream> using namespace std; const int MAXN=110; int N,M; struct Node { int number,p;//p:该结点的possible;number:该结点的bug数 }; Node node[MAXN];//记录结点 int dp[MAXN][MAXN];//DP,dp[i][j]表示跟结点为i时,用掉j个士兵获得的最大值 int adj[MAXN][MAXN];//存树 。adj[i][j]:结点为i,adj[i][0]表示该结点所连接的结点(父结点和子结点一共)个数 //adj[i][j](j>=1)表示结点编号,j=结点个数+1 bool vis[MAXN];//访问标记 int max(int a, int b) { return a>b ? a:b; } void dfs(int root)//DFS,求该结点及其分支所能获得的最大possible { vis[root]=true;//已经访问 int num=(node[root].number+19)/20;//获得该结点需要的士兵数目 for(int i=num;i<=M;i++) dp[root][i]=node[root].p;//用掉i个士兵获得的possible for(i=1;i<=adj[root][0];i++) { int u=adj[root][i]; if(vis[u]) continue;//跳过已访问的,包括该结点的父节点和子结点 dfs(u);//求该子结点的最大possible for(int j=M;j>=num;j--) { for(int k=1;j+k<=M;k++)//剩余的士兵 { if(dp[u][k])//该子结点的最大possible dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);//j+k:父节点和子结点共用了士兵数目 //dp[root][j+k]父结点和前i-1个子结点中所获possible的最大值 //dp[root][j]+dp[u][k]父结点和当前子结点u一共所获possible //用来找出所有子结点里能得到的最大possible //即该父结点能得到的最大possible } } } } int main() { int b,e; while(cin >> N >> M) { if(N==-1&&M==-1) break; memset(vis,false,sizeof(vis)); memset(dp,0,sizeof(dp)); memset(adj,0,sizeof(adj)); for(int i=1;i<=N;i++) cin >> node[i].number >>node[i].p; for(i=1;i<N;i++)//存图 { cin >> b >> e;//连接结点b和e adj[b][0]++; adj[b][adj[b][0]]=e; adj[e][0]++; adj[e][adj[e][0]]=b; } if(M==0)//这个必需要,有代价为0的房间,M=0则无法获得 cout << 0 << endl; else { dfs(1); cout << dp[1][M] << endl; } } return 0; }

上一篇:HDU 4597 Play Game 2013 ACM-ICPC吉林通化全国邀请赛H题
下一篇:在用户空间发生中断时,上下文切换的过程

相关文章

相关评论