#
[題目描述]
有一個n*n的迷宮，每個方格里都有著相應的數字。你從左上角出發，每次可以向上下左右四個方向最多移動k格，并且要求你每次到達的方格里的數字必須大于上一次所在方格的數字。現在要求你走過的方格的所有數之和最大，問這個最大和是多少。
[輸入]
輸入數據第一行為兩個正整數N、K（1<=N<=100,0<=K<=N）
接下來的n行，每行有n個不超過integer范圍的整數，表示地圖中的數。
[輸出]
輸出數據只有一行，為最大的和。
[輸入輸出示例]
輸入(maze.in) 輸出(maze.out)
3 1 25
3 6 2
4 7 9
2 3 1
[評分標準]
對于每個測試數據，如果你能夠得出正確的答案，那么你將得到滿分，否則得0分。
[分析]
很明顯的動態規劃，應該是從《滑雪》那道題改編而來的。
1: #include <stdio.h>
2: #define maxn 110
3:
4: int a[maxn][maxn];
5: int f[maxn][maxn];
6: int n,ans,k;
7: int xx[4]={0,0,1,-1};
8: int yy[4]={1,-1,0,0};
9:
10: int find(int x,int y)
11: {
12: if (f[x][y]) return f[x][y];
13: int temx,temy;
14: for (int i=0;i<4;++i)
15: for (int j=1;j<=k;++j)
16: {
17: temx=x+xx[i]*j;
18: temy=y+yy[i]*j;
19: if ((temx>0)&&(temx<=n)&&(temy>0)&&(temy<=n))
20: if ((a[temx][temy]>a[x][y])&&(find(temx,temy)>f[x][y]))
21: f[x][y]=find(temx,temy);
22: }
23: f[x][y]+=a[x][y];
24: return f[x][y];
25: }
26:
27: int main()
28: {
29: freopen("maze.in","r",stdin);
30: freopen("maze.out","w",stdout);
31:
32: scanf("%d%d",&n,&k);
33: for (int i=1;i<=n;++i)
34: for (int j=1;j<=n;++j)
35: scanf("%d",&a[i][j]);
36: printf("%d\n",find(1,1));
37: return 0;
38: }
39:
請了一個長沙第一中學的老師，很出名。大概帶出來了幾百個省一吧。
從今天開始進入為期5天的“長沙一中學習”專題活動~
也許這幾天用不了writer了，因為安裝的時候ms要重新啟動。西區的電腦有還原卡的。
To be continued.
【問題描述】
做過了乘積最大這道題，相信這道題也難不倒你。
已知一個數串，可以在適當的位置加入乘號（設加了k個，當然也可不加，即分成k+1個部分），設這k+1個部分的乘積（如果k=0,則乘積即為原數串的值）對m 的余數（即mod m）為x;
現求x能達到的最小值及該情況下k的最小值，以及x能達到的最大值及該情況下的k的最小值（可以存在x的最小值與最大值相同的情況）。
【輸入】
第一行為數串，長度為n 滿足2<=n<=1000，且數串中不存在0；
第二行為m，滿足2<=m<=50。
【輸出】
四個數，分別為x的最小值 和 該情況下的k，以及x的最大值和 該情況下的k，中間用空格隔開。
【樣例輸入】
4421
22
【樣例輸出】
0 1 21 0
既然題目要求的都是乘號的最小值，那么我們自然地就會想到動歸數組中記錄乘號的最小值。f[i][j]表示0~i的串達到j這個余數所需最少的乘號數。預處理b[i][j]表示從i到j的數對m的余數。
1: #include <stdio.h>
2: #include <string.h>
3: #define MAXINT 100000
4: #define maxn 1010
5:
6: int f[maxn][50];
7: int b[maxn][maxn];
8: int n,m;
9: char s[maxn];
10: int tem;
11:
12: int main()
13: {
14: freopen("input.txt","r",stdin);
15: freopen("output.txt","w",stdout);
16:
17: scanf("%s%d",s,&m);
18: n=strlen(s);
19: for (int i=0;i<n;++i)
20: for (int j=0;j<m;++j)
21: f[i][j]=MAXINT;
22: for (int i=0;i<n;++i)
23: {
24: tem=(tem*10+s[i]-'0')%m;
25: f[i][tem]=0;
26: }
27: for (int i=0;i<n;++i)
28: {
29: tem=0;
30: for (int j=i;j<n;++j)
31: {
32: tem=(tem*10+s[j]-'0')%m;
33: b[i][j]=tem;
34: }
35: }
36: for (int i=0;i<n;++i)
37: for (int j=0;j<m;++j)
38: if (f[i][j]<MAXINT)
39: for (int k=i+1;k<n;++k)
40: {
41: tem=(j*b[i+1][k])%m;
42: if (f[i][j]+1<f[k][tem]) f[k][tem]=f[i][j]+1;
43: }
44: for (int i=0;i<m;++i)
45: if (f[n-1][i]<MAXINT)
46: {
47: printf("%d %d ",i,f[n-1][i]);
48: break;
49: }
50: for (int i=m-1;i>=0;--i)
51: if (f[n-1][i]<MAXINT)
52: {
53: printf("%d %d\n",i,f[n-1][i]);
54: break;
55: }
56: return 0;
57: }
58:
【問題描述】
n個人在做傳遞物品的游戲,編號為1-n。
游戲規則是這樣的：開始時物品可以在任意一人手上，他可把物品傳遞給其他人中的任意一位；下一個人可以傳遞給未接過物品的任意一人。
即物品只能經過同一個人一次，而且每次傳遞過程都有一個代價；不同的人傳給不同的人的代價值之間沒有聯系；
求當物品經過所有n個人后，整個過程的總代價是多少。
【輸入】
第一行為n,表示共有n個人（16>=n>=2）；
以下為n*n的矩陣，第i+1行、第j列表示物品從編號為i的人傳遞到編號為j的人所花費的代價，特別的有第i+1行、第i列為-1（因為物品不能自己傳給自己），其他數據均為正整數(<=10000)。
(對于50%的數據，n<=11)。
【輸出】
一個數，為最小的代價總和。
【樣例輸入】
2
-1 9794
2724 –1
【樣例輸出】
2724
時間到了啊~ 明天再繼續寫。
是一個用二進制來表示圖的狀態的動態規劃，或者說是記憶化搜索。f[i][j]中，i來表示圖的二進制狀態，j表示這個狀態中第一個點。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 20
4: #define MAXINT 1000000
5: using namespace std;
6:
7: int dis[maxn][maxn];
8: int n;
9: int f[70000][20];
10: int ans=MAXINT;
11:
12: int find(int a,int b)
13: {
14: if (f[a][b]!=MAXINT) return f[a][b];
15: int tem=a;
16: a-=(1<<b);
17: if (!a)
18: {
19: f[tem][b]=0;
20: return 0;
21: }
22: for (int i=0;i<n;++i)
23: if ((1<<i)&a)
24: f[tem][b]=min(find(a,i)+dis[b][i],f[tem][b]);
25: return f[tem][b];
26: }
27:
28: int main()
29: {
30: freopen("input.txt","r",stdin);
31: freopen("output.txt","w",stdout);
32:
33: scanf("%d",&n);
34: for (int i=0;i<n;++i)
35: for (int j=0;j<n;++j)
36: scanf("%d",&dis[i][j]);
37: for (int i=0;i<(1<<n);++i)
38: for (int j=0;j<n;++j)
39: f[i][j]=MAXINT;
40: for (int i=0;i<n;++i)
41: if (find((1<<n)-1,i)<ans)
42: ans=find((1<<n)-1,i);
43: printf("%d\n",ans);
44: return 0;
45: }
46:
【問題描述】
天蒼蒼，野茫茫，JSZX的菜鳥們來到OI牧場旅游，看到了好多好多的牛。OI牧場所有的牛都覺得自己的Rp最高（簡稱RP牛），為此他們常爭論不休。于是，他們讓JSZX的菜菜們用最最樸素的方法找出這只RP牛。
經過討論，最菜的mmk想出了最樸素的方法：
我們要以cows的名字為線索，來找出RP牛。
首先，得到n頭牛的名字清單（每頭牛的名字是一個僅包含小寫字母的字符串，且這些牛的讀寫方式比較特殊—從右到左），然后對每頭牛進行檢驗，檢驗按照牛的讀寫方式進行。規則如下：
1．Rp 牛的名字中必須有子串“jszxoier”
2．將名字中的每個“cow”的替換為“bird”。
3．計算Rp值：A為名字中子串“r”的個數；
B為名字中子串“p”的個數；
C為名字中字串“rp”的個數；
Rp值即為5×A+5×B+20×C。
最后輸出RP牛的名字，若有多個RP牛，則輸出名字最短的那個。
假如你也是牛中一員，盡管你很不屑這樣的水題，但是，你很想到RP牛那里分點Rp，所以你決定解決這道題，并算出RP牛的Rp是多少。
【輸入】
第一行，一個數n（n<=3000）。
接下來的n行，每行一個字符串，長度<=300，數據保證存在RP牛。
【輸出】
共兩行
第一行為RP牛的名字
第二行為RP牛的Rp值
【樣例輸入】
8
reioxzsjzmy
mmk
jwc
zxf
jwc
wangwei
xcy
yuhc
【樣例輸出】
reioxzsjzmy
5
我用KMP匹配的，代碼挺短，還比string.h的好用。
1: #include <stdio.h>
2: #include <string.h>
3: #include <iostream>
4: #define maxn 400
5: using namespace std;
6:
7: int f[maxn];
8: char *aa="jszxoier",*bb="cow",*ee="rp",s[maxn];
9: int a,b,c,tem,ans,anslen,len,m;
10: int n;
11: bool t;
12: char anss[400];
13:
14: void initf(char *s)
15: {
16: memset(f,0,sizeof(f));
17: m=strlen(s);
18: int k=-1;
19: f[0]=-1;
20: for (int i=1;i<m;++i)
21: {
22: while ((k>-1)&&(s[k+1]!=s[i])) k=f[k];
23: if (s[k+1]==s[i]) ++k;
24: f[i]=k;
25: }
26: }
27:
28: void changef(char *s)
29: {
30: initf(s);
31: int k;
32: for (int i=0;i<m;++i)
33: {
34: k=f[i];
35: while ((k>-1)&&(s[k+1]==s[i+1])) k=f[k];
36: f[i]=k;
37: }
38: }
39:
40: int main()
41: {
42: freopen("input.txt","r",stdin);
43: freopen("output.txt","w",stdout);
44:
45: scanf("%d",&n);
46: for (int dt=1;dt<=n;++dt)
47: {
48: memset(s,0,sizeof(s));
49: scanf("%s",s);
50: strrev(s);
51: changef(aa);
52: len=strlen(s);
53: int k=-1;
54: t=0;
55: for (int i=0;i<len;++i)
56: {
57: while ((k>-1)&&(aa[k+1]!=s[i])) k=f[k];
58: if (aa[k+1]==s[i]) ++k;
59: if (k==m-1)
60: {
61: t=1;
62: break;
63: }
64: }
65: if (!t) continue;
66: a=b=c=0;
67: changef(bb);
68: for (int i=0;i<len;++i)
69: {
70: while ((k>-1)&&(bb[k+1]!=s[i])) k=f[k];
71: if (bb[k+1]==s[i]) ++k;
72: if (k==m-1) ++a;
73: }
74: for (int i=0;i<len;++i)
75: if (s[i]=='r') ++a;
76: for (int i=0;i<len;++i)
77: if (s[i]=='p') ++b;
78: changef(ee);
79: for (int i=0;i<len;++i)
80: {
81: while ((k>-1)&&(ee[k+1]!=s[i])) k=f[k];
82: if (ee[k+1]==s[i]) ++k;
83: if (k==m-1) ++c;
84: }
85: tem=a*5+b*5+c*20;
86: if (tem>ans)
87: {
88: memset(anss,0,sizeof(anss));
89: strcat(anss,s);
90: ans=tem;
91: anslen=len;
92: }
93: else
94: if (tem==ans)
95: if (len<anslen)
96: {
97: memset(anss,0,sizeof(anss));
98: strcat(anss,s);
99: }
100: }
101: strrev(anss);
102: printf("%s\n%d\n",anss,ans);
103: return 0;
104: }
105:
I play tricks on others,and others play tircks on me.
It’s the story.It’s the world.That’s common.
Nothing serious.
Just..
nothing…
還是 沒有找準位置呢。
Sephiroth，我是多么渴望成為他一樣的男人啊。
找了兩節課的衣服……就是為了找到依托吧。信仰什么的，在某個時候已經崩潰了。
寶貝兒，對不起，沒有給你打電話。本來不想寫出來的，但是…… 自己現在這個狀態，真的是連自己都放心不下。爸爸媽媽一直都在擔心……
Sephiroth，當初取這個名字，是希望成為他一樣強大的男人。
……
…………
………………
哈，只是在裝的憂郁對不對,Sephiroth？…………
又一經典問題，noip2001。
用到了分類的思想。對于f[i][j]代表i分為j份。我們分為以下兩類：
- 每份都沒有1：那么我們只需要將每份都減1然后保證有j份。即加上f[i-j][j]。
- 至少有一份1：那么我們提出1個1,即加上f[i-1][j-1]。
1: #include <stdio.h>
2: #define maxn 300
3:
4: int f[maxn][maxn];
5: int n,m;
6:
7: int main()
8: {
9: scanf("%d%d",&n,&m);
10: f[0][0]=1;
11: for (int i=1;i<=n;++i)
12: for (int j=1;j<=m;++j)
13: if (i-j>=0)
14: f[i][j]=f[i-j][j]+f[i-1][j-1];
15: printf("%d\n",f[n][m]);
16: return 0;
17: }
18:
很經典的問題，由于遞推公式比較詭異，所以特地的記錄下來。
1: #include <stdio.h>
2: #define maxn 100
3:
4: unsigned long long f[maxn];
5: int n,m;
6:
7: int main()
8: {
9: f[0]=1;
10: scanf("%d%d",&n,&m);
11: for (int i=1;i<=n;++i)
12: {
13: f[i]=f[i-1]*2;
14: if (i-m-1>=0) f[i]-=f[i-m-1];
15: if (i-m-1==-1) f[i]-=1;
16: }
17: printf("%I64d\n",f[n]);
18: return 0;
19: }
20: