Bribing FIPA(树形DP)输入难，学会stringstream的用法，map的使用-白红宇

Bribing FIPA(树形DP)输入难，学会stringstream的用法，map的使用

阅读量：4036 次

发布时间：2019-05-24

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

1、

用vector时一定注意clear();又因为这个错了。。。

2、题目大意：

有n个国家，现在Benjamin Bennett想要获得m张票，一个国家只有一张票，现在他准备用钻石来交换票，求要想获得m张票最少用多少钻石交换，已知这些国家彼此有关系，假如a是b的父亲，b是c的父亲，那么获得a的票了，那么相当于bc的也获得了

注意可能获得m+1张票的代价要比获得m张票小，

与poj 1155类似

dp[i][j]表示以i为根获得j张票的最小代价

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

输入比较难，看网上的代码用的stringstream，还没看懂

3、AC代码：

#include
   
    #include
    
     #include
     #include
      
       #include 
       
        #include
        
         #include
         
          using namespace std;#define N 205#define INF 1000000000int cost[N],num[N];vector
          
            adj[N*2];int in[N],vis[N];int dp[N][N],m,n;int dfs(int u){ vis[u]=1; int cnt=1; for(int j=0; j<=n; j++)dp[u][j]=INF;//注意是j<=n,可能超过m个国家用的钻石少 dp[u][0]=0; for(int i=0; i
           
            =0; j--) { for(int k=1; k<=j; k++) { dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]); } } } if(dp[u][cnt]>cost[u]) dp[u][cnt]=cost[u]; return cnt;}int main(){ char str[1000]; while(gets(str)) { if(str[0]=='#') break; sscanf(str,"%d%d",&n,&m); map
            
              Map; int id=0; memset(in,0,sizeof(in)); memset(vis,0,sizeof(vis)); //注意clear() for(int i=0;i<=n;i++) adj[i].clear(); for(int i=0; i
             
              >name) { if(Map.find(name)==Map.end()) Map[name]=++id; int v=Map[name]; adj[u].push_back(v); in[v]++; } } cost[0]=INF; for(int i=1; i<=n; i++) { if(in[i]) continue; adj[0].push_back(i); } dfs(0); int ans=INF; for(int i=m; i<=n; i++) { if(dp[0][i]

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

你可能感兴趣的文章