四塔問題

【描述】

“漢諾塔”，是一個眾所周知的古老游戲。現在我們把問題稍微改變一下：如果一共有4根柱子，而不是3根，那么至少需要移動盤子多少次，才能把所有的盤子從第1根柱子移動到第4根柱子上呢？

為了編程方便，您只需要輸出這個結果mod 10000的值。

【輸入】

一個正整數n。（0<n<=50000）

【輸出】

一個正整數，表示把n個盤子從第1根柱子移動到第4根柱子需要的最少移動次數mod 10000的值。

【樣例輸入】

15

【樣例輸出】

129

【分析】

弄出前幾個數，發現規律。

f[1]=1，之后分別是加2個2，加3個4，加4個8，加5個16……

  1: #include <stdio.h>
  2: #define maxn 50010
  3: 
  4: int a,b;
  5: int k=1,t;
  6: long long j=1;
  7: int n;
  8: 
  9: int main()
 10: {
 11:     freopen("hnoi.in","r",stdin);
 12:     freopen("hnoi.out","w",stdout);
 13:     
 14:     scanf("%d",&n);
 15:     b=1;
 16:     for (int i=2;i<=n;++i)
 17:     {
 18:         a=b;
 19:         if (!t)
 20:         {
 21:             t=++k;
 22:             j*=2;
 23:             j%=10000;
 24:         }
 25:         b=(a+j)%10000;
 26:         --t;
 27:     }
 28:     printf("%d\n",b);
 29:     return 0;
 30: }
 31: 

posted @ 2010-09-02 11:27 Sephiroth Lee 閱讀(330) | 評論 (0) | 編輯 收藏

動態規劃-工業時代

【試題描述】

小FF的第一片礦區已經開始運作了， 他著手開展第二片礦區……

小FF的第二片礦區， 也是”NewBe_One“計劃的核心部分， 因為在這片礦區里面有全宇宙最稀有的兩種礦物，科學家稱其為NEW礦和BE礦。

礦區是被劃分成一個n*m的矩形區域。 小FF探明了每一小塊區域里的NEW礦和BE礦的蘊藏量， 并且小FF還在礦區的北邊和西邊分別設置了NEW礦和BE礦的收集站。你的任務是設計一個管道運輸系統，使得運送的NEW礦和BE礦的總量最多。

管道的型號有兩種，一種是東西向，一種是南北向。在一個格子內你能建造一種管道，但丌能兩種都建。如果兩個同類型管道首位相接，它們就可以被連接起來。

另外這些礦物都十分丌穩定，因此它們在運送過程中都丌能拐彎。這就意味著如果某個格子上建有南北向管道，但是它北邊的格子建有東西向管道，那么這根南北向管道內運送的任何東西都將丟失。迚一步地，運到NEW礦收集站的BE礦也會丟失，運到BE礦收集站的NEW礦也會丟失。

【輸入格式】

第一行包含兩個整數n和m，表示礦區大小。

以下n行，每行m個整數，其中第i行第j個整數G[ i , j ] 描述各個格子上的BE礦數量。接下來以類似的矩陣表示各個格子上的NEW礦數量。

【輸出格式】

僅一個整數， 表示最多可以采集到的NEW礦和BE礦的總量。

【輸入樣例】

4 4

0 0 10 9

1 3 10 0

4 2 1 3

1 1 20 0

10 0 0 0

1 1 1 30

0 0 5 5

5 10 10 10

【輸出樣例】

98

【數據范圍】

對于30%的數據： 0<= n，m <=100;

對于100%的數據： 0<= n, m <=1000;

0<= G[ i, j ] <=1000.

【分析】

每個點只有兩種狀態，放be的管道或者放new的管道。

  1: #include <stdio.h>
  2: #include <iostream>
  3: #define maxn 1010
  4: using namespace std;
  5: 
  6: int g[maxn][maxn][2];
  7: long long f[maxn][maxn][2];
  8: int ne[maxn][maxn],be[maxn][maxn];
  9: int n,m;
 10: 
 11: int main()
 12: {
 13:     freopen("industry.in","r",stdin);
 14:     freopen("industry.out","w",stdout);
 15:     
 16:     scanf("%d%d",&n,&m);
 17:     for (int i=1;i<=n;++i)
 18:         for (int j=1;j<=m;++j)
 19:             scanf("%d",&g[i][j][0]);
 20:     for (int i=1;i<=n;++i)
 21:         for (int j=1;j<=m;++j)
 22:             scanf("%d",&g[i][j][1]);
 23:     for (int i=1;i<=n;++i)
 24:         for (int j=1;j<=m;++j)
 25:         {
 26:             ne[i][j]=ne[i-1][j]+g[i][j][1];
 27:             be[i][j]=be[i][j-1]+g[i][j][0];
 28:         }
 29:     for (int i=1;i<=n;++i)
 30:         for (int j=1;j<=m;++j)
 31:         {
 32:             f[i][j][0]=be[i][j]+max(f[i-1][j][0],f[i-1][j][1]);
 33:             f[i][j][1]=ne[i][j]+max(f[i][j-1][1],f[i][j-1][0]);
 34:         }
 35:     printf("%lld\n",max(f[n][m][1],f[n][m][0]));
 36:     return 0;
 37: }
 38: 

posted @ 2010-09-02 07:24 Sephiroth Lee 閱讀(278) | 評論 (0) | 編輯 收藏

動態規劃-田忌賽馬

【描述】

中國古代的歷史故事“田忌賽馬”是為大家所熟知的。話說齊王和田忌又要賽馬了，他們各派出N匹馬，每場比賽，輸的一方將要給贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢。現在每匹馬的速度值是固定而且已知的，而齊王出馬也不管田忌的出馬順序。請問田忌該如何安排自己的馬去對抗齊王的馬，才能贏取最多的錢？

【輸入】

第一行為一個正整數n (n <= 2000) ，表示雙方馬的數量。

第二行有N個整數表示田忌的馬的速度。

第三行的N個整數為齊王的馬的速度。

【輸出】

僅有一行，為田忌賽馬可能贏得的最多的錢，結果有可能為負。

【樣例輸入】

3

92 83 71

95 87 74

【樣例輸出】

200

【分析】

如果齊王的馬是按速度排序之后，從高到低被派出的話，田忌一定是將他馬按速度排序之后，從兩頭取馬去和齊王的馬比賽。

n設f[i,j]表示齊王按從強到弱的順序出馬和田忌進行了i場比賽之后，從“頭”取了j匹較強的馬，從“尾”取了i-j匹較弱的馬，所能夠得到的最大盈利。

n狀態轉移方程如下：

nF[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}

n其中g[i,j]表示田忌的馬和齊王的馬分別按照由強到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利，勝為200，輸為－200，平為0。

  1: #include <stdio.h>
  2: #include <limits.h>
  3: #include <stdlib.h>
  4: #define maxn 1010
  5: 
  6: int a[maxn],b[maxn];
  7: int g[maxn][maxn];
  8: int f[2][maxn];
  9: int n,er;
 10: int ans;
 11: 
 12: int cmp(const void*a,const void*b)
 13: {
 14:     int c=*(int*)a,d=*(int*)b;
 15:     if (c<d) return 1;
 16:     if (c>d) return -1;
 17:     return 0;
 18: }
 19: 
 20: int main()
 21: {
 22:     scanf("%d",&n);
 23:     for (int i=1;i<=n;++i) scanf("%d",&b[i]);
 24:     for (int i=1;i<=n;++i) scanf("%d",&a[i]);
 25:     a[0]=b[0]=INT_MAX;
 26:     qsort(a,n+1,sizeof(int),cmp);
 27:     qsort(b,n+1,sizeof(int),cmp);
 28:     for (int i=1;i<=n;++i)
 29:         for (int j=1;j<=n;++j)
 30:             if (a[i]>b[j]) g[i][j]=-200;
 31:             else
 32:                 if (a[i]<b[j]) g[i][j]=200;
 33:     for (int i=1;i<=n;++i)
 34:     {
 35:         er^=1;
 36:         for (int j=0;j<=i;++j)
 37:         {
 38:             f[er][j]=f[er^1][j]+g[i][n-i+j+1];
 39:             if (j)
 40:                 if (f[er^1][j-1]+g[i][j]>f[er][j])
 41:                     f[er][j]=f[er^1][j-1]+g[i][j];
 42:         }
 43:     }
 44:     for (int i=0;i<=n;++i)
 45:         if (f[er][i]>ans)
 46:             ans=f[er][i];
 47:     printf("%d\n",ans);
 48:     return 0;
 49: }
 50: 

posted @ 2010-09-02 06:25 Sephiroth Lee 閱讀(1976) | 評論 (0) | 編輯 收藏

“長沙一中學習”-day2

今天上午講的是線性的動歸。講的例題有：

1. 機器分配模型
2. 船
3. 樓梯問題
4. 田忌賽馬
5. 最長公共子串

然后就是有關矩形的動態規劃。如下：

1. 滑雪
2. 工業時代

還有區間類的：

1. 凸多邊形劃分
2. 最大乘積
3. 石子合并（用到了四邊形不等式）
4. 數字游戲

然后有三道測試題：

1. 四塔問題
2. 關燈
3. 任務安排

下午開始將樹形的動態規劃。

1. 聚會的快樂
2. 三色二叉樹
3. 皇宮看守
4. 珠寶
5. 符文之旅（最小與最大）

沒有寫的題目以后會逐步完成。

posted @ 2010-09-01 21:54 Sephiroth Lee 閱讀(142) | 評論 (0) | 編輯 收藏

樹形動態規劃-三色二叉樹

【問題描述】

一棵二叉樹可以按照如下規則表示成一個由0、1、2 組成的字符序列，我們稱之為“二叉樹序列S”：

2表示該樹有兩個子節點， 和分別表示其兩個子樹的二叉樹序列

1表示該樹有一個子節點， 為其子樹的二叉樹序列

0表示該樹沒有子節點

你的任務是要對一棵二叉樹的節點進行染色。每個節點可以被染成紅色、綠色或藍色。并且，一個節點與其子節點的顏色必須不同，如果該節點有兩個子節點，那么這兩個子節點的顏色也必須不相同。給定一棵二叉樹的二叉樹序列，請求出這棵樹中最多和最少有多少個點能夠被染成綠色。

【輸入文件】

輸入文件名：TRO.IN

輸入文件僅有一行，不超過10000 個字符，表示一個二叉樹序列。

【輸出文件】

輸出文件名：TRO.OUT

輸出文件也只有一行，包含兩個數，依次表示最多和最少有多少個點能夠被

染成綠色。

【樣例輸入】

1122002010

【樣例輸出】

5 2

【分析】

1.動歸分析

拿最大來說。

每個節點的狀態只有三種顏色，我們用f[i][0],f[i][1]分別代表第i個點染綠色和不然綠色的最多的點數。因為如果一個點不染綠色，那么他染另兩種顏色是等價的。如此我們就得到了如下的動規方程：

• 葉子：f[i][0]=1; f[i][1]=0;
• 一個子節點：f[i][0]=f[子節點][1]; f[i][1]=max(f[子節點][0],f[子節點][1]);
• 兩個子節點：f[i][0]=f[左兒子][1]+f[右兒子][1]; f[i][1]=max(f[左兒子][1]+f[右兒子][0],f[左兒子][0]+f[右兒子][1]);

最后輸出就是max(f[0][1],f[0][0])。

最小的和最大的相同。

2.樹的確定

因為是一棵二叉樹的前序遍歷，那么對于一個有子節點的點來說，左兒子就是i+1。我們引進一個link[i]，表示以i為根的子樹最后一個點的標號，那么r[i]=link[l[i]]+1。

對于link[l]，我們如此確定：

• 葉子：link[l]=l;
• 一個子節點：link[l]=link[l+1];
• 兩個子節點：link[l]=link[link[l+1]+1];

然后就是實現了。因為自己弄得還是不是很熟，打了兩節課。

  1: #include <stdio.h>
  2: #include <string.h>
  3: #include <iostream>
  4: #define maxn 10010
  5: #define MAXINT 10000000
  6: using namespace std;
  7: 
  8: char s[maxn];
  9: int f[maxn][2];
 10: int link[maxn];
 11: int n;
 12: int l[maxn],r[maxn];
 13: 
 14: int _find(int x)
 15: {
 16:     if (link[x]) return link[x];
 17:     if (s[x]=='0') link[x]=x;
 18:     else
 19:         if (s[x]=='1') link[x]=_find(x+1);
 20:         else
 21:             link[x]=_find(_find(x+1)+1);
 22:     return link[x];
 23: }
 24: 
 25: void find1(int x)
 26: {
 27:     if (f[x][0]) return;
 28:     if (s[x]=='0')
 29:     {
 30:         f[x][0]=1;
 31:         f[x][1]=0;
 32:     }
 33:     else
 34:         if (s[x]=='1')
 35:         {
 36:             find1(l[x]);
 37:             f[x][0]=f[l[x]][1]+1;
 38:             f[x][1]=max(f[l[x]][1],f[l[x]][0]);
 39:         }
 40:         else
 41:         {
 42:             find1(l[x]);
 43:             find1(r[x]);
 44:             f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
 45:             f[x][1]=max(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
 46:         }
 47: }
 48: 
 49: void find2(int x)
 50: {
 51:     if (f[x][0]<MAXINT) return;
 52:     if (s[x]=='0')
 53:     {
 54:         f[x][0]=1;
 55:         f[x][1]=0;
 56:     }
 57:     else
 58:         if (s[x]=='1')
 59:         {
 60:             find2(l[x]);
 61:             f[x][0]=f[l[x]][1]+1;
 62:             f[x][1]=min(f[l[x]][1],f[l[x]][0]);
 63:         }
 64:         else
 65:         {
 66:             find2(l[x]);
 67:             find2(r[x]);
 68:             f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
 69:             f[x][1]=min(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
 70:         }
 71: }
 72: 
 73: int main()
 74: {
 75:     freopen("tro.in","r",stdin);
 76:     freopen("tro.out","w",stdout);
 77:     
 78:     scanf("%s",s);
 79:     n=strlen(s);
 80:     _find(0);
 81:     for (int i=0;i<n;++i)
 82:     {
 83:         l[i]=i+1;
 84:         r[i]=link[l[i]]+1;
 85:     }
 86:     find1(0);
 87:     printf("%d ",max(f[0][0],f[0][1]));
 88:     for (int i=0;i<n;++i)
 89:         f[i][0]=f[i][1]=MAXINT;
 90:     find2(0);
 91:     printf("%d\n",min(f[0][0],f[0][1]));
 92:     return 0;
 93: }
 94: 

posted @ 2010-09-01 21:41 Sephiroth Lee 閱讀(778) | 評論 (0) | 編輯 收藏

區間類動態規劃-數字游戲

題目網上都可以找到。

注意初始化s[i][j]的時候要加上100000而不是10！！！我傻叉子了= =

  1: #include <stdio.h>
  2: #define MAXINT 10000000
  3: #define maxn 200
  4: 
  5: int f[maxn][maxn][maxn][2];//0 max|||| 1 min
  6: int s[maxn][maxn];
  7: int a[maxn];
  8: int n,m;
  9: int maxans,minans=MAXINT;
 10: 
 11: void find(int x,int y,int t)
 12: {
 13:     if (f[x][y][t][0]) return;
 14:     if (t==1)
 15:     {
 16:         f[x][y][1][0]=f[x][y][1][1]=s[x][y];
 17:         return;
 18:     }
 19:     for (int k=x+t-1-1;k<y;++k)
 20:     {
 21:         find(x,k,t-1);
 22:         if (f[x][k][t-1][1]*s[k+1][y]<f[x][y][t][1]) f[x][y][t][1]=f[x][k][t-1][1]*s[k+1][y];
 23:         if (f[x][k][t-1][0]*s[k+1][y]>f[x][y][t][0]) f[x][y][t][0]=f[x][k][t-1][0]*s[k+1][y];
 24:     }
 25: }
 26: 
 27: int main()
 28: {
 29:     freopen("game.in","r",stdin);
 30:     freopen("game.out","w",stdout);
 31:     
 32:     scanf("%d%d",&n,&m);
 33:     for (int i=1;i<=n;++i)
 34:     {
 35:         scanf("%d",&a[i]);
 36:         a[i+n]=a[i];
 37:     }
 38:     for (int i=1;i<=2*n;++i)
 39:         for (int j=i;j<=2*n;++j)
 40:             for (int k=1;k<=m;++k)
 41:                 f[i][j][k][1]=MAXINT;
 42:     for (int i=1;i<=2*n;++i)
 43:         for (int j=i;j<=2*n;++j)
 44:             s[i][j]=(s[i][j-1]+a[j]+100000)%10;
 45:     for (int i=1;i<=n;++i) find(i,i+n-1,m);
 46:     for (int i=1;i<=n;++i)
 47:     {
 48:         if (f[i][i+n-1][m][0]>maxans) maxans=f[i][i+n-1][m][0];
 49:         if (f[i][i+n-1][m][1]<minans) minans=f[i][i+n-1][m][1];
 50:     }
 51:     printf("%d\n%d\n",minans,maxans);
 52:     return 0;
 53: }
 54: 

posted @ 2010-09-01 21:40 Sephiroth Lee 閱讀(351) | 評論 (0) | 編輯 收藏

數學問題-Black and White

【題目描述】

尋找一個由n個整數組成的數列，其中任意連續p個整數之和為正，任意連續q個整數之和為負。若不存在這樣的整數數列，則輸出NO，否則輸出其中一個數列。

【輸入】

對于每個測試點將給你M組數據，要求你對于每組數據，判斷是否存在這樣的整數數列。

輸入的第一行是一個正整數M，（1<=N<=10000）,接下來的M行對應M組數據，每行有三個正整數N、P、Q（1<=n,p,q<=10^8）。

【輸出】

輸出數據共N行，每行為yes或者no，如果第I組數據有解，則在第I行輸出yes，否則輸出no

【輸入輸出示例】

【評分標準】

對于每個測試點，如果你能夠在1S內通過每組數據，你將得到這個測試點的分數，否則，這個測試點你只能得0分。

【分析】

原題目是要求輸出一種可能的解，如果沒有解就輸出-1。這樣的話就要用到差分約束。

現在的話，只需要一個公式。如果有解，應滿足：n<=q+p-gcd(p,q)-1。

  1: #include <stdio.h>
  2: #include <iostream>
  3: using namespace std;
  4: 
  5: int n,m,p,q;
  6: 
  7: int gcd(int a,int b)
  8: {
  9:     if (a<b) swap(a,b);
 10:     int t;
 11:     while (b!=0)
 12:     {
 13:         t=a;
 14:         a=b;
 15:         b=t%a;
 16:     }
 17:     return a;
 18: }
 19: 
 20: int main()
 21: {
 22:     freopen("sequence.in","r",stdin);
 23:     freopen("sequence.out","w",stdout);
 24:     
 25:     scanf("%d",&m);
 26:     for (int i=0;i<m;++i)
 27:     {
 28:         scanf("%d%d%d",&n,&p,&q);
 29:         if (n<=p+q+gcd(p,q)-1) printf("YES\n");
 30:         else printf("NO\n");
 31:     }
 32:     return 0;
 33: }
 34: 

下面是我寫的查分約束。

  1: #include <stdio.h>
  2: #define MAXINT 1000000
  3: #define maxn 1010
  4: 
  5: struct ss
  6: {
  7:     int x,y,dis;
  8: } l[10000];
  9: 
 10: int s[maxn];
 11: int a[maxn];
 12: int d[maxn];
 13: int n,q,p,tot;
 14: 
 15: int main()
 16: {
 17:     scanf("%d%d%d",&n,&p,&q);
 18:     for (int i=0;i<=n;++i)
 19:         if (i+p>n) break;
 20:         else
 21:         {
 22:             l[++tot].x=i+p;
 23:             l[tot].y=i;
 24:             l[tot].dis=-1;
 25:         }
 26:     for (int i=0;i<=n;++i)
 27:         if (i+q>n) break;
 28:         else
 29:         {
 30:             l[++tot].x=i;
 31:             l[tot].y=i+q;
 32:             l[tot].dis=-1;
 33:         }
 34:     for (int i=1;i<=n;++i)
 35:     {
 36:         for (int j=1;j<=tot;++j)
 37:             if (d[l[j].y]>d[l[j].x]+l[j].dis)
 38:                 d[l[j].y]=d[l[j].x]+l[j].dis;
 39:         for (int j=1;j<=tot;++j)
 40:             if (d[l[j].y]>d[l[j].x]+l[j].dis)
 41:             {
 42:                 printf("-1\n");
 43:                 return 0;
 44:             }
 45:     }
 46:     for (int i=0;i<=n;++i)
 47:         s[i]=d[i];
 48:     for (int i=1;i<=n;++i) printf("%d\n",s[i]-s[i-1]);
 49:     return 0;
 50: }
 51: 

posted @ 2010-09-01 07:00 Sephiroth Lee 閱讀(158) | 評論 (0) | 編輯 收藏

“長沙一中學習”-day1

今天上午從東區搬東西到西區。11點都收拾完了，然后到水房潑了一個小時的水。

下午兩點多的時候曹老師開始講課。

今天的課程是兩個內容：全面分析試題，動態規劃。

曹老師拿他給自己的學生布置的任務做例子，大概的說了一下從一個題目的模型到完整的題目的過程。首先曹老師給了4道題目，都只是大概的描述。然后將每個條件定嚴謹。確定輸入輸出的格式。分析可以用什么算法，每種算法的時間復雜度以及可以通過的數據范圍。根據算法定出數據，寫出標程。曹老師說他們的學生每個人通過自己的分析，做出10個數據，然后大概100多個測試點來測試每個人寫的程序。

以下是4道題目。第二題有些瓶頸，一會再發。

1. 動態規劃-走迷宮問題
2. 空缺
3. 貪心-買彩票
4. 數學問題-Black and White

posted @ 2010-08-31 20:09 Sephiroth Lee 閱讀(134) | 評論 (0) | 編輯 收藏

數學問題-Black and White

【題目描述】

尋找一個由n個整數組成的數列，其中任意連續p個整數之和為正，任意連續q個整數之和為負。若不存在這樣的整數數列，則輸出NO，否則輸出其中一個數列。

【輸入】

對于每個測試點將給你M組數據，要求你對于每組數據，判斷是否存在這樣的整數數列。

輸入的第一行是一個正整數M，（1<=N<=10000）,接下來的M行對應M組數據，每行有三個正整數N、P、Q（1<=n,p,q<=10^8）。

【輸出】

輸出數據共N行，每行為yes或者no，如果第I組數據有解，則在第I行輸出yes，否則輸出no

【輸入輸出示例】

【評分標準】

對于每個測試點，如果你能夠在1S內通過每組數據，你將得到這個測試點的分數，否則，這個測試點你只能得0分。

【分析】

原題目是要求輸出一種可能的解，如果沒有解就輸出-1。這樣的話就要用到差分約束。

現在的話，只需要一個公式。如果有解，應滿足：n<=q+p+gcd(p,q)-1。

  1: #include <stdio.h>
  2: #include <iostream>
  3: using namespace std;
  4: 
  5: int n,m,p,q;
  6: 
  7: int gcd(int a,int b)
  8: {
  9:     if (a<b) swap(a,b);
 10:     int t;
 11:     while (b!=0)
 12:     {
 13:         t=a;
 14:         a=b;
 15:         b=t%a;
 16:     }
 17:     return a;
 18: }
 19: 
 20: int main()
 21: {
 22:     freopen("sequence.in","r",stdin);
 23:     freopen("sequence.out","w",stdout);
 24:     
 25:     scanf("%d",&m);
 26:     for (int i=0;i<m;++i)
 27:     {
 28:         scanf("%d%d%d",&n,&p,&q);
 29:         if (n<=p+q+gcd(p,q)-1) printf("YES\n");
 30:         else printf("NO\n");
 31:     }
 32:     return 0;
 33: }
 34: 

posted @ 2010-08-31 19:59 Sephiroth Lee 閱讀(160) | 評論 (0) | 編輯 收藏

貪心-買彩票

【問題描述】

電視里面正放著“抽百萬大獎，贏幸福生活”的宣傳廣告，bird看后也想去試試手氣，當然，作為經濟學院的高材生，他可不屑只是單純的去碰運氣。經過他的一番分析，發現，商家在彩票里面做了手腳，使得每個抽獎點的中獎概率不是完全一樣的，而且隨著時間的變化而變化，不過這種變化是有規律的。對于第I個抽獎點，最開始的中獎概率是百萬分之Pi，以后每抽一張彩票后都要重新排隊，花費的時間是T分鐘，每抽一次減少的概率為Di。

由于可憐的bird還有一大堆的作業沒做，他只能抽出H個小時去買彩票。由于抽獎地點都在一路公共汽車的線路上，所以怕麻煩的bird決定按車站順序抽獎，當然，bird可以從任意一站開始抽獎，對于經過的抽獎點可以買彩票，也可以不買。假設從第I個抽獎點到第I+1個抽獎點需要做Ci分鐘的汽車。

Bird希望能在有限的H個小時內獲得最好的運氣——即抽獎的概率和最大。

[輸入] 輸入文件名：(tickt.in)

第一行為一個整數n，表示抽獎點的個數，1<=n<=200

第二行是兩個整數H和T，1<=H<=10，1<=T<=60。

接下來的n行，每行3個整數，分別是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。

[輸出] 輸出文件名：(tickt.out)

文件僅有一行，為一個整數，即抽獎概率和的最大值。

【輸入輸出樣例】

【樣例說明】

首先，bird從1號開始抽獎，花費20分鐘，得到概率200，然后坐車到2號，花費10分鐘，再花20分鐘得到概率300，概率和是500，花費50分鐘。

【評分標準】

對于每個測試點，如果你能夠在規定的時間內通過每組數據，你將得到這個測試點的分數，否則，這個測試點你只能得0分。

【分析】

由CEOI的釣魚改編，具體可以看《算法藝術與信息學競賽》P13。

  1: #include <stdio.h>
  2: #include <iostream>
  3: #define maxn 210
  4: using namespace std;
  5: 
  6: int b[maxn][maxn];
  7: int p[maxn],d[maxn],c[maxn];
  8: int h,t,tot;
  9: struct ss
 10: {
 11:     int pi,di;
 12: } hp[maxn];
 13: int remain,ans,teans,n;
 14: 
 15: void down(int x)
 16: {
 17:     int te=2*x;
 18:     while (te<=tot)
 19:     {
 20:         if ((te+1<=tot)&&(hp[te].pi<hp[te+1].pi)) ++te;
 21:         if (hp[x].pi>hp[te].pi) break;
 22:         swap(hp[x],hp[te]);
 23:         x=te;
 24:         te=x*2;
 25:     }
 26: }
 27: 
 28: int main()
 29: {
 30:     freopen("ticket.in","r",stdin);
 31:     freopen("ticket.out","w",stdout);
 32:     
 33:     scanf("%d%d%d",&n,&h,&t);
 34:     h*=60;
 35:     for (int i=1;i<=n;++i) scanf("%d%d%d",&p[i],&d[i],&c[i]);
 36:     for (int i=1;i<=n;++i)
 37:         for (int j=i+1;j<=n;++j)
 38:             b[i][j]=b[i][j-1]+c[j-1];
 39:     for (int i=1;i<=n;++i)
 40:         for (int j=n;j>=i;--j)
 41:         {
 42:             teans=0;
 43:             remain=h-b[i][j];
 44:             memset(hp,0,sizeof(hp));
 45:             for (int k=1;k<=j-i+1;++k)
 46:             {
 47:                 hp[k].pi=p[i+k-1];
 48:                 hp[k].di=d[i+k-1];
 49:             }
 50:             tot=j-i+1;
 51:             for (int k=j-i+1;k>=1;--k) down(k);
 52:             while ((remain>=t)&&(hp[1].pi>0))
 53:             {
 54:                 teans+=hp[1].pi;
 55:                 hp[1].pi-=hp[1].di;
 56:                 remain-=t;
 57:                 down(1);
 58:             }
 59:             if (teans>ans) ans=teans;
 60:         }
 61:     printf("%d\n",ans);
 62:     return 0;
 63: }
 64: 

posted @ 2010-08-31 19:55 Sephiroth Lee 閱讀(355) | 評論 (0) | 編輯 收藏