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 }
posted @
2012-03-04 10:29 Leo.W 閱讀(300) |
評論 (0) |
編輯 收藏 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 }
posted @
2012-03-03 01:23 Leo.W 閱讀(157) |
評論 (0) |
編輯 收藏 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
posted @
2012-03-03 01:21 Leo.W 閱讀(477) |
評論 (0) |
編輯 收藏 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
posted @
2012-03-02 23:59 Leo.W 閱讀(265) |
評論 (0) |
編輯 收藏
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 }
posted @
2012-03-02 14:48 Leo.W 閱讀(857) |
評論 (0) |
編輯 收藏