#
[題目描述]
有一個(gè)n*n的迷宮，每個(gè)方格里都有著相應(yīng)的數(shù)字。你從左上角出發(fā)，每次可以向上下左右四個(gè)方向最多移動(dòng)k格，并且要求你每次到達(dá)的方格里的數(shù)字必須大于上一次所在方格的數(shù)字。現(xiàn)在要求你走過的方格的所有數(shù)之和最大，問這個(gè)最大和是多少。
[輸入]
輸入數(shù)據(jù)第一行為兩個(gè)正整數(shù)N、K（1<=N<=100,0<=K<=N）
接下來的n行，每行有n個(gè)不超過integer范圍的整數(shù)，表示地圖中的數(shù)。
[輸出]
輸出數(shù)據(jù)只有一行，為最大的和。
[輸入輸出示例]
輸入(maze.in) 輸出(maze.out)
3 1 25
3 6 2
4 7 9
2 3 1
[評(píng)分標(biāo)準(zhǔn)]
對(duì)于每個(gè)測(cè)試數(shù)據(jù)，如果你能夠得出正確的答案，那么你將得到滿分，否則得0分。
[分析]
很明顯的動(dòng)態(tài)規(guī)劃，應(yīng)該是從《滑雪》那道題改編而來的。
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:
請(qǐng)了一個(gè)長(zhǎng)沙第一中學(xué)的老師，很出名。大概帶出來了幾百個(gè)省一吧。
從今天開始進(jìn)入為期5天的“長(zhǎng)沙一中學(xué)習(xí)”專題活動(dòng)~
也許這幾天用不了writer了，因?yàn)榘惭b的時(shí)候ms要重新啟動(dòng)。西區(qū)的電腦有還原卡的。
To be continued.
【問題描述】
做過了乘積最大這道題，相信這道題也難不倒你。
已知一個(gè)數(shù)串，可以在適當(dāng)?shù)奈恢眉尤氤颂?hào)（設(shè)加了k個(gè)，當(dāng)然也可不加，即分成k+1個(gè)部分），設(shè)這k+1個(gè)部分的乘積（如果k=0,則乘積即為原數(shù)串的值）對(duì)m 的余數(shù)（即mod m）為x;
現(xiàn)求x能達(dá)到的最小值及該情況下k的最小值，以及x能達(dá)到的最大值及該情況下的k的最小值（可以存在x的最小值與最大值相同的情況）。
【輸入】
第一行為數(shù)串，長(zhǎng)度為n 滿足2<=n<=1000，且數(shù)串中不存在0；
第二行為m，滿足2<=m<=50。
【輸出】
四個(gè)數(shù)，分別為x的最小值 和 該情況下的k，以及x的最大值和 該情況下的k，中間用空格隔開。
【樣例輸入】
4421
22
【樣例輸出】
0 1 21 0
既然題目要求的都是乘號(hào)的最小值，那么我們自然地就會(huì)想到動(dòng)歸數(shù)組中記錄乘號(hào)的最小值。f[i][j]表示0~i的串達(dá)到j(luò)這個(gè)余數(shù)所需最少的乘號(hào)數(shù)。預(yù)處理b[i][j]表示從i到j(luò)的數(shù)對(duì)m的余數(shù)。
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個(gè)人在做傳遞物品的游戲,編號(hào)為1-n。
游戲規(guī)則是這樣的：開始時(shí)物品可以在任意一人手上，他可把物品傳遞給其他人中的任意一位；下一個(gè)人可以傳遞給未接過物品的任意一人。
即物品只能經(jīng)過同一個(gè)人一次，而且每次傳遞過程都有一個(gè)代價(jià)；不同的人傳給不同的人的代價(jià)值之間沒有聯(lián)系；
求當(dāng)物品經(jīng)過所有n個(gè)人后，整個(gè)過程的總代價(jià)是多少。
【輸入】
第一行為n,表示共有n個(gè)人（16>=n>=2）；
以下為n*n的矩陣，第i+1行、第j列表示物品從編號(hào)為i的人傳遞到編號(hào)為j的人所花費(fèi)的代價(jià)，特別的有第i+1行、第i列為-1（因?yàn)槲锲凡荒茏约簜鹘o自己），其他數(shù)據(jù)均為正整數(shù)(<=10000)。
(對(duì)于50%的數(shù)據(jù)，n<=11)。
【輸出】
一個(gè)數(shù)，為最小的代價(jià)總和。
【樣例輸入】
2
-1 9794
2724 –1
【樣例輸出】
2724
時(shí)間到了啊~ 明天再繼續(xù)寫。
是一個(gè)用二進(jìn)制來表示圖的狀態(tài)的動(dòng)態(tài)規(guī)劃，或者說是記憶化搜索。f[i][j]中，i來表示圖的二進(jìn)制狀態(tài)，j表示這個(gè)狀態(tài)中第一個(gè)點(diǎn)。
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牧場(chǎng)旅游，看到了好多好多的牛。OI牧場(chǎng)所有的牛都覺得自己的Rp最高（簡(jiǎn)稱RP牛），為此他們常爭(zhēng)論不休。于是，他們讓JSZX的菜菜們用最最樸素的方法找出這只RP牛。
經(jīng)過討論，最菜的mmk想出了最樸素的方法：
我們要以cows的名字為線索，來找出RP牛。
首先，得到n頭牛的名字清單（每頭牛的名字是一個(gè)僅包含小寫字母的字符串，且這些牛的讀寫方式比較特殊—從右到左），然后對(duì)每頭牛進(jìn)行檢驗(yàn)，檢驗(yàn)按照牛的讀寫方式進(jìn)行。規(guī)則如下：
1．Rp 牛的名字中必須有子串“jszxoier”
2．將名字中的每個(gè)“cow”的替換為“bird”。
3．計(jì)算Rp值：A為名字中子串“r”的個(gè)數(shù)；
B為名字中子串“p”的個(gè)數(shù)；
C為名字中字串“rp”的個(gè)數(shù)；
Rp值即為5×A+5×B+20×C。
最后輸出RP牛的名字，若有多個(gè)RP牛，則輸出名字最短的那個(gè)。
假如你也是牛中一員，盡管你很不屑這樣的水題，但是，你很想到RP牛那里分點(diǎn)Rp，所以你決定解決這道題，并算出RP牛的Rp是多少。
【輸入】
第一行，一個(gè)數(shù)n（n<=3000）。
接下來的n行，每行一個(gè)字符串，長(zhǎng)度<=300，數(shù)據(jù)保證存在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…
還是 沒有找準(zhǔn)位置呢。
Sephiroth，我是多么渴望成為他一樣的男人啊。
找了兩節(jié)課的衣服……就是為了找到依托吧。信仰什么的，在某個(gè)時(shí)候已經(jīng)崩潰了。
寶貝兒，對(duì)不起，沒有給你打電話。本來不想寫出來的，但是…… 自己現(xiàn)在這個(gè)狀態(tài)，真的是連自己都放心不下。爸爸媽媽一直都在擔(dān)心……
Sephiroth，當(dāng)初取這個(gè)名字，是希望成為他一樣強(qiáng)大的男人。
……
…………
………………
哈，只是在裝的憂郁對(duì)不對(duì),Sephiroth？…………
又一經(jīng)典問題，noip2001。
用到了分類的思想。對(duì)于f[i][j]代表i分為j份。我們分為以下兩類：
- 每份都沒有1：那么我們只需要將每份都減1然后保證有j份。即加上f[i-j][j]。
- 至少有一份1：那么我們提出1個(gè)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:
很經(jīng)典的問題，由于遞推公式比較詭異，所以特地的記錄下來。
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: