本文共 814 字，大约阅读时间需要 2 分钟。

1、

2、题目大意;

有n个洞穴，每个洞穴中有相应的价值和bugs,现在有m个士兵，每个士兵可以消灭20个bugs,求这m个士兵最多可以获得多少价值

dp[i][j]表示以i为根用掉j个士兵获得的最大价值

 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);

3、AC代码：

#include
   
    #include
    
     using namespace std;#include
     
      #include
      
       #define N 105vector
       
         adj[N*2];int dp[N][N];int w[N],val[N],vis[N],m;void dfs(int u){    vis[u]=1;    for(int i=w[u];i<=m;i++)    dp[u][i]=val[u];    for(int i=0;i
        
         =w[u];j--) { for(int k=1;k<=j-w[u];k++)//k从1开始，从0wrong { dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]); } } } }}int main(){ int n,a,b; while(scanf("%d%d",&n,&m)!=EOF) { if(n==-1 && m==-1) break; for(int i=0;i<=n;i++) { adj[i].clear(); } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d%d",&w[i],&val[i]); w[i]=(w[i]+19)/20; //dp[i][w[i]]=val[i]; } for(int i=1;i
        
       
      
     
    
   

转载地址：http://lrddi.baihongyu.com/