#
[题目描述]
有一个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: