1 /*
 2 Author:    Leo.W
 3 Descriptipn:  给定一个树形的地图，用最少的树节点使得能够控制【即所有结点都能一个被占据的结点相连】全树。  
 4 How to Do:    dp[i][0]=sum{dp[son[i][j]][1]};
 5             dp[i][1]=sum{min(dp[son[i][j]][0],dp[son[i][j]][1])};
 6             建立结构体，对输入的信息，记录子树的个数及序号，初始是根节点
 7   */
 8 #include <iostream>
 9 using namespace std;
10 #define MAXSIZE 1501
11 int dp[MAXSIZE][2];//对于每一个结点的选择，放或不放，两种
12 struct node{
13     int num[MAXSIZE];
14     int lenth;
15     bool isAnc;
16 };
17 node nd[MAXSIZE];
18 inline int mins(int a,int b){
19     return a<b?a:b;
20 }
21 int dfs(int no,int alter){//序号及二选一的选择
22     if(dp[no][alter]!=INT_MIN)
23         return dp[no][alter];
24     int i,temp=nd[no].lenth;
25     int sum=0;
26     sum+=alter;
27     for(i=0;i<temp;i++){
28         int son=nd[no].num[i];
29         if(alter)
30             sum+=mins(dfs(son,0),dfs(son,1));
31         else
32             sum+=dfs(son,1);
33     }
34     return dp[no][alter]=sum;
35 }
36 int main(){
37     //freopen("in.txt","r",stdin);
38     int n;
39     while(scanf("%d",&n)!=EOF){
40         int i,j;
41         for(i=0;i<n;i++){
42             dp[i][0]=dp[i][1]=INT_MIN;
43             nd[i].isAnc=true;
44         }
45         for(i=0;i<n;i++){
46             int nodeNo,nodeNum;
47             scanf("%d:(%d)",&nodeNo,&nodeNum);
48             nd[nodeNo].lenth=nodeNum;
49             for(j=0;j<nodeNum;j++){
50                 int temp;
51                 scanf("%d",&temp);
52                 nd[nodeNo].num[j]=temp;
53                 nd[temp].isAnc=false;
54             }
55         }
56         for(i=0;i<n;i++)
57             if(nd[i].isAnc)
58                 break;
59         int ans=mins(dfs(i,0),dfs(i,1));
60         printf("%d\n",ans);
61     }
62     return 0;
63 }

 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    一个容量为V的大包，装价值为m1，体积为v1的物品（m2,v2;m3,v3;mn,vn），
 4                 共n种物品，每种限取一个，试求得到最大价值。
 5 How to Do:    f[V]=max{f[V],f[V-c[i]]+w[i]}
 6   */
 7 #include <iostream>
 8 #include <string.h>
 9 using namespace std;
10 #define MAXSIZE 1002
11 int c[MAXSIZE],w[MAXSIZE],f[MAXSIZE];
12 int main(){
13     //freopen("in.txt","r",stdin);
14     int t;
15     scanf("%d",&t);
16     while(t--){
17         int n,vol;
18         scanf("%d%d",&n,&vol);
19         int i,j;
20         for(i=0;i<n;i++)    scanf("%d",&w[i]);//价值
21         for(i=0;i<n;i++)    scanf("%d",&c[i]);//体积
22         memset(f,0,sizeof(f));
23         for(i=0;i<n;i++){
24             for(j=vol;j>=c[i];j--){
25                 f[j]=f[j]>(f[j-c[i]]+w[i])?f[j]:(f[j-c[i]]+w[i]);
26             }
27         }
28         printf("%d\n",f[vol]);
29     }
30     return 0;
31 }

 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    典型的完全背包题。三种不同价值的物品，不限每种商品取得次数，在限定的预订n内，得到的最大价值
 4 How to Do:    f[V]=max{f[V-k*c[i]]+k*c[i]}
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 using namespace std;
 9 int f[10001];
10 int main(){
11     //freopen("in.txt","r",stdin);
12     int t;
13     scanf("%d",&t);
14     while(t--){
15         int m;
16         scanf("%d",&m);
17         int i,j;
18         int c[3]={150,200,350};
19         memset(f,0,sizeof(f));
20         for(i=0;i<3;i++){
21             for(j=c[i];j<=m;j++){
22                 int k=1,max=f[j];
23                 //以下的while循环体是关键代码
24                 while(j-k*c[i]>=0){//测试k值是满足题意的
25                     if((f[j-k*c[i]]+k*c[i])>max&&(f[j-k*c[i]]+k*c[i])<=j)//此处限定的范围很关键
26                         max=f[j-k*c[i]]+k*c[i];
27                     k++;
28                 }
29                 f[j]=max;
30             }
31         }
32         printf("%d\n",m-f[m]);
33     }
34     return 0;
35 }
36 

 1 /*
 2 Author:    Leo.W
 3 Descriptipn:典型的01背包问题，对输入的每组数据【花费及可能性】进行背包判断，
 4             得到在花费总和是经济能力范围内的累计获offer几率最大的组合。
 5 How to Do:f[V]=max{f[V],f[V-c[i]]+w[i]}; 
 6         【前后f[V]分别表示前i个大学申请在总花费为V时的最大几率和前i-1个大学申请在总花费为V时的最大几率；
 7             f[V-c[i]]表示前i-1个大学在总花费为V-c[i]时的最大几率，
 8             c[i]表示第i个大学申请的花费，w[i]则表示第i个大学申请成功的几率】
 9   */
10 #include <iostream>
11 #include <string.h>
12 using namespace std;
13 double f[100010];
14 int c[1010];
15 double w[1010];
16 int main(){
17     //freopen("in.txt","r",stdin);
18     int n,m;
19     int i,j;
20     while(scanf("%d%d",&n,&m),m||n){
21         for(i=0;i<m;i++){
22             scanf("%d%lf",&c[i],&w[i]);
23         }
24         memset(f,0.0,sizeof(f));
25         for(i=0;i<m;i++){
26             for(j=n;j>=c[i];j--){//比较是鉴于概率论的知识
27                 f[j]=f[j]>(1-(1-f[j-c[i]])*(1-w[i]))?f[j]:(1-(1-f[j-c[i]])*(1-w[i]));
28             }
29         }
30         double sum=f[n]*100;
31         printf("%.1lf%%\n",sum);
32     }
33     return 0;
34 }
35 

 1 /*

 2 Author:    Leo.W

 3 Descriptipn:对输入字符串【长度不知，仅含26个大写英文字母和一个空格表示符‘_’，共27种字符】,

 4             统计每种字符出现频度，按哈夫曼编码原理给出最小的编码位数之和，得出与8位固定字长

 5             编码的比率【保留一位小数】。

 6 How to Do:    哈夫曼编码原理的理解及优先队列的运用<priority_queue>,引用头文件<queue>

 7   */

 8 #include <iostream>

 9 #include <string.h>

10 #include <queue>

11 #include <algorithm>

12 using namespace std;

13 #define lenth 300

14 int main(){

15     //freopen("in.txt","r",stdin);

16     char str[1000];//输入字符串

17     while(scanf("%s",str),strcmp(str,"END")!=0){

18         int lenStr=strlen(str);

19         int worse=lenStr<<3;//固定字长编码所需的总位数

20         char ch[lenth];int lenCh=0;//输入字符的种类

21         int i,j,num[lenth];//对应每种字符的数目，无需关注具体对应的是哪个字符，只需记录数目即可。【为什么呢？】

22         memset(num,0,lenth);//字符数目数组初始置零

23         //对字符串逐个统计出现次数

24         for(i=0;i<lenStr;i++){

25             for(j=0;j<lenCh;j++){

26                 if(str[i]==ch[j]){

27                     num[j]++;break;

28                 }

29             }

30             if(j==lenCh){

31                 ch[j]=str[i];num[j]++;lenCh++;

32             }

33         }

34         sort(num,num+lenCh);//对得到的字符数目【大于零，即至少出现过一次，才存在统计必要】序列进行升序快排

35         priority_queue<int,vector<int>,greater<int> >    que;//对于int整型数据，进行自小至大的优先级排列

36         for(i=0;i<lenCh;i++)    que.push(num[i]);

37         int sum=0;

38         while(true){

39             int aa=que.top();    que.pop();

40             if(que.empty())    {

41                 if(lenCh==1)    sum=aa;

42                 break;

43             }

44             int bb=que.top();    que.pop();

45             sum+=aa+bb;        que.push(aa+bb);

46         }

47         printf("%d %d %.1lf\n",worse,sum,worse*1.0/sum);

48     }

49     return 0;

50 }