四塔問題

【描述】

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

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

【輸入】

一個正整數(shù)n。（0<n<=50000）

【輸出】

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

【樣例輸入】

15

【樣例輸出】

129

【分析】

弄出前幾個數(shù)，發(fā)現(xiàn)規(guī)律。

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 閱讀(320) | 評論 (0) | 編輯 收藏

動態(tài)規(guī)劃-工業(yè)時代

【試題描述】

小FF的第一片礦區(qū)已經(jīng)開始運作了， 他著手開展第二片礦區(qū)……

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

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

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

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

【輸入格式】

第一行包含兩個整數(shù)n和m，表示礦區(qū)大小。

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

【輸出格式】

僅一個整數(shù)， 表示最多可以采集到的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

【數(shù)據(jù)范圍】

對于30%的數(shù)據(jù)： 0<= n，m <=100;

對于100%的數(shù)據(jù)： 0<= n, m <=1000;

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

【分析】

每個點只有兩種狀態(tài)，放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 閱讀(265) | 評論 (0) | 編輯 收藏

動態(tài)規(guī)劃-田忌賽馬

【描述】

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

【輸入】

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

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

第三行的N個整數(shù)為齊王的馬的速度。

【輸出】

僅有一行，為田忌賽馬可能贏得的最多的錢，結(jié)果有可能為負(fù)。

【樣例輸入】

3

92 83 71

95 87 74

【樣例輸出】

200

【分析】

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

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

n狀態(tài)轉(zhuǎ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 閱讀(1943) | 評論 (0) | 編輯 收藏

“長沙一中學(xué)習(xí)”-day2

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

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

然后就是有關(guān)矩形的動態(tài)規(guī)劃。如下：

1. 滑雪
2. 工業(yè)時代

還有區(qū)間類的：

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

然后有三道測試題：

1. 四塔問題
2. 關(guān)燈
3. 任務(wù)安排

下午開始將樹形的動態(tài)規(guī)劃。

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

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

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

樹形動態(tài)規(guī)劃-三色二叉樹

【問題描述】

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

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

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

0表示該樹沒有子節(jié)點

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

【輸入文件】

輸入文件名：TRO.IN

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

【輸出文件】

輸出文件名：TRO.OUT

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

染成綠色。

【樣例輸入】

1122002010

【樣例輸出】

5 2

【分析】

1.動歸分析

拿最大來說。

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

• 葉子：f[i][0]=1; f[i][1]=0;
• 一個子節(jié)點：f[i][0]=f[子節(jié)點][1]; f[i][1]=max(f[子節(jié)點][0],f[子節(jié)點][1]);
• 兩個子節(jié)點：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.樹的確定

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

對于link[l]，我們?nèi)绱舜_定：

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

然后就是實現(xiàn)了。因為自己弄得還是不是很熟，打了兩節(jié)課。

  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 閱讀(756) | 評論 (0) | 編輯 收藏

區(qū)間類動態(tài)規(guī)劃-數(shù)字游戲

題目網(wǎng)上都可以找到。

注意初始化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 閱讀(329) | 評論 (0) | 編輯 收藏

數(shù)學(xué)問題-Black and White

【題目描述】

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

【輸入】

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

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

【輸出】

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

【輸入輸出示例】

【評分標(biāo)準(zhǔn)】

對于每個測試點，如果你能夠在1S內(nèi)通過每組數(shù)據(jù)，你將得到這個測試點的分?jǐn)?shù)，否則，這個測試點你只能得0分。

【分析】

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

現(xiàn)在的話，只需要一個公式。如果有解，應(yīng)滿足：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 閱讀(145) | 評論 (0) | 編輯 收藏

“長沙一中學(xué)習(xí)”-day1

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

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

今天的課程是兩個內(nèi)容：全面分析試題，動態(tài)規(guī)劃。

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

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

1. 動態(tài)規(guī)劃-走迷宮問題
2. 空缺
3. 貪心-買彩票
4. 數(shù)學(xué)問題-Black and White

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

數(shù)學(xué)問題-Black and White

【題目描述】

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

【輸入】

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

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

【輸出】

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

【輸入輸出示例】

【評分標(biāo)準(zhǔn)】

對于每個測試點，如果你能夠在1S內(nèi)通過每組數(shù)據(jù)，你將得到這個測試點的分?jǐn)?shù)，否則，這個測試點你只能得0分。

【分析】

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

現(xiàn)在的話，只需要一個公式。如果有解，應(yīng)滿足：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 閱讀(145) | 評論 (0) | 編輯 收藏

貪心-買彩票

【問題描述】

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

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

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

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

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

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

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

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

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

【輸入輸出樣例】

【樣例說明】

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

【評分標(biāo)準(zhǔn)】

對于每個測試點，如果你能夠在規(guī)定的時間內(nèi)通過每組數(shù)據(jù)，你將得到這個測試點的分?jǐn)?shù)，否則，這個測試點你只能得0分。

【分析】

由CEOI的釣魚改編，具體可以看《算法藝術(shù)與信息學(xué)競賽》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 閱讀(330) | 評論 (0) | 編輯 收藏