NOIP复习篇———枚举
打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。
游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了，所以你改装了锤子，增加了锤子与地面的接触面积，使其每次可以击打一片区域。如果我们把地面看做m*n的方阵，其每个元素都代表一个地鼠洞，那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点：每次挥舞锤子时，对于这R*C的区域中的所有地洞，锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中，每个地洞必须至少有1只地鼠，且如果某个地洞中地鼠的个数大于1，那么这个地洞只会有1只地鼠被打掉，因此每次挥舞锤子时，恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密，因此在游戏过程中你不能旋转锤子（即不能互换R和C）。
你可以任意更改锤子的规格（即你可以任意规定R和C的大小），但是改装锤子的工作只能在打地鼠前进行（即你不可以打掉一部分地鼠后，再改变锤子的规格）。你的任务是求出要想打掉所有的地鼠，至少需要挥舞锤子的次数。
Hint：由于你可以把锤子的大小设置为1*1，因此本题总是有解的。
第一行包含两个正整数m和n；
下面m行每行n个正整数描述地图，每个数字表示相应位置的地洞中地鼠的数量。
输出一个整数，表示最少的挥舞次数。
3 3
1 2 1
2 4 2
1 2 1
4
使用2*2的锤子，分别在左上、左下、右上、右下挥舞一次。
对于30%的数据，m,n≤5；
对于60%的数据，m,n≤30；
对于100%的数据，m,n≤100，其他数据不小于0，不大于105。
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=101;
- int g[MaxN][MaxN],allsum=0;
- int n,m,r,c,ans=0x7fffffff;
- int tmp[MaxN][MaxN];
- bool ok(){
- int i,j,i1,j1;
- for(i=1;i<=n;i++)
- for(j=1;j<=m;j++)
- tmp[i][j]=g[i][j];
- for(i=1;i<=n;i++)//枚举中心点
- for(j=1;j<=m;j++)
- if(tmp[i][j]){
- if(i+r<=n+1 && j+c<=m+1){
- int delta=tmp[i][j];
- for(i1=0;i1<r;i1++)
- for(j1=0;j1<c;j1++)
- tmp[i+i1][j+j1]-=delta;
- if(tmp[i1+i][j1+j]<0)return false;
- }
- else return false;
- }
- return true;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(r=1;r<=n;r++)
- for(c=1;c<=m;c++)
- {
- scanf("%d",&g[r][c]);
- allsum+=g[r][c];
- }
- for(r=1;r<=n;r++)//枚举锤子的长宽
- for(c=1;c<=m;c++)
- {
- if(allsum%(r*c)==0 && allsum/(r*c)<ans && ok()==true)
- ans=allsum/(r*c);
- }
- cout<<ans;
- return 0;
- }
Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V<
span>，且不存在Jam数字P，使U<P<V<
span>）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。
有2行，第1行为3个正整数，用一个空格隔开：
s t w
（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s<T<
span>≤26, 2≤w≤t-s ）
第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。
所给的数据都是正确的，不必验证。
最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格
2 10 5
bdfij
bdghi
bdghj
bdgij
bdhij
befgh
#分析#
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=300;
- char str[MaxN];
- int s,t,w,l;
- int main(){
- int i;
- cin>>s>>t>>w;
- scanf("%s",str);
- l=strlen(str)-1;
- for(i=1;i<=5;i++){
- int j=l;
- while(j>=0 && str[j]==t+97+j-w)j--;
- if(j==-1)break;
- str[j]++;
- for(int k=j+1;k<=w-1;k++)str[k]=str[k-1]+1;
- cout<<str<<endl;
- }
- return 0;
- }
《合数和》
用户输入一个数，然后输出从1开始一直到这个数为止（包括这个数）中所有的合数的和。
一个整数N，0<N<=1000
一行，一个整数，即从1到N中所有合数的和
样例一：100
样例二：9
样例一：3989
样例二：27
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=1001;
- int p[MaxN],sum,n;
- int getans(){
- int i,j;
- memset(p,1,sizeof(p));
- for(i=2;i<=n;i++)
- if(p[i])
- for(j=i*i;j<=n;j+=i)
- p[j]=0;
- for(i=2;i<=n;i++)
- if(!p[i])sum+=i;
- return sum;
- }
- int main(){
- scanf("%d",&n);
- cout<<getans();
- return 0;
- }
1.3 枚举算法的反思
NOIP复习篇———贪心
贪心算法，是指人们为了解决问题而下意识的为自己的最大利益而设计的方案，往往题目中会出现“最小”“最大”等关键词，而贪心算法的最大难度莫过于证明贪心和想出贪心策略，对于NOIP普及组的难度，不会考察这点..举个简单的例子，人们在穿越草地时往往选择直线穿过（两点之间，线段最短），这便是贪心算法。
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
第一行D1 C D2 P N
之后N行，每行2个数表示离出发点的距离Di和每升汽油的价格Pi
最消费用，保留2位小数
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
26.95
N<=100
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=101;
- int n;
- double d1,c,go,price_start;
- double now,ans,minway,d;
- struct oil{
- double dis,price;
- friend bool operator< (oil a,oil b){return a.price<b.price;}
- }s[MaxN];
- int main(){
- int i,k,p;
- cin>>d1>>c>>go>>price_start>>n;
- for(i=1;i<=n;i++)cin>>s[i].dis>>s[i].price;
- sort(s+1,s+n+1);
- s[k=0].dis=0;
- s[k].price=price_start;
- s[n+1].dis=d1;
- s[n+1].price=0;
- while(now<d1){
- minway=(double)(0x7fffffff);
- p=-1;
- for(i=1;i<=n+1;i++)
- if(i!=k && s[k].price>s[i].price && c*go+s[k].dis>=s[i].dis && minway>(s[i].dis-s[k].dis) && s[i].dis>s[k].dis){
- minway=s[i].dis-s[k].dis;
- p=i;
- }
- if(p!=-1){
- ans+=((s[p].dis-s[k].dis)/go-d)*s[k].price;
- now=s[p].dis;
- k=p;
- }
- else {
- if(((s[k+1].dis-s[k].dis)/go)>c){cout<<"No Solution";return 0;}
- ans+=(c-d)*s[k].price;//在此站把油加满
- d=c-(s[k+1].dis-s[k].dis)/go;
- now=s[k+1].dis;
- k++;
- }
- }
- printf("%.2lf",ans);
- return 0;
- }
给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。
输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。
输出第一行是一个整数表示最多剩下的线段数。
3
6 3
1 3
2 5
2
0<N<100
#分析#
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=1000001;
- struct line{
- int L,R;
- friend bool operator< (line a,line b){return a.R<b.R;}
- }a[MaxN];
- int ans,n,i,MAX;
- int main(){
- freopen("line.in","r",stdin);
- freopen("line.out","w",stdout);
- scanf("%d",&n);
- for(i=1;i<=n;i++){
- scanf("%d %d",&a[i].L,&a[i].R);
- if(a[i].L>a[i].R)swap(a[i].L,a[i].R);
- }
- sort(a+1,a+n+1);
- MAX=-(1<<30);
- for(i=1;i<=n;i++){
- if(MAX<=a[i].L){
- ans++;
- MAX=a[i].R;
- }
- }
- printf("%d",ans);
- return 0;
- }
3.《线段覆盖三步曲第三步——线段覆盖3》
在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分（端点可以重合），问最大的k为多少。
输入格式
输入文件的第1行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。
输出格式
输出文件仅包括1个整数，为k的最大值
3
0 2
2 4
1 3
2
数据范围
对于20%的数据，n≤10；
对于50%的数据，n≤1000；
对于70%的数据，n≤100000；
对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。
王钢是一名学习成绩优异的学生，在平时的学习中，他总能利用一切时间认真高效地学习，他不但学习刻苦，而且善于经常总结、完善自己的学习方法，所以他总能在每次考试中得到优异的分数，这一切很大程度上是由于他是一个追求效率的人。
但王钢也是一个喜欢玩的人，平时在学校学习他努力克制自己玩，可在星期天他却会抽一定的时间让自己玩一下，他的爸爸妈妈也比较信任他的学习能力和学习习惯，所以在星期天也不会象其他家长一样对他抓紧，而是允许他在星期天上午可以*支配时间。
地鼠游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多地鼠来，然后等你用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。问题是这些地鼠不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个地鼠冒出后停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同，为了胜出，游戏参与者就必须根据每个地鼠的特性，有选择地尽快敲击一些地鼠，使得总的得分最大。
这个极具挑战性的游戏王钢特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个地鼠所需要的耗时是1秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个地鼠冒出来后停留的时间都是固定的，而且他记录了每个地鼠被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序地选择敲击不同的地鼠，保证每次得到最大的总分值。
输入包含3行，第一行包含一个整数n（1<=n<=100）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间，第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值（<=100）。每行中第i个数都表示第i个地鼠的信息。
输出只有一行一个整数，表示王钢所能获得的最大游戏总分值。
5
5 3 6 1 4
7 9 2 1 5
24
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=10001;
- struct mice{
- int time,score;
- friend bool operator< (mice a,mice b){return a.time<b.time;}
- }g[MaxN];
- priority_queue<int > q;
- int n,ans=0;
- int main(){
- freopen("mouse.in","r",stdin);
- freopen("mouse.out","w",stdout);
- int i,j,MAX=0;
- cin>>n;
- for(i=1;i<=n;i++){cin>>g[i].time;MAX=max(MAX,g[i].time);}
- for(i=1;i<=n;i++)cin>>g[i].score;
- sort(g+1,g+n+1);
- j=n;
- for(i=MAX;i>=1;i--)
- {
- while(j>0 && g[j].time==i){q.push(g[j].score);j--;}
- if(!q.empty()){ans+=q.top();q.pop();}
- }
- cout<<ans;
- return 0;
- }
NOIP复习篇———动态规划
1.1 动态规划
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）
输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
7
389 207 155 300 299 170 158 65
6
2
导弹的高度<=30000，导弹个数<=20
- //朴素O(N^2)代码
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int a[30000];
- int n=1,i,j,max1;
- int f[600000];
- int main()
- {
- while(scanf("%d",&a[n++])!=EOF);
- n--;
- f[1]=1;
- for(i=2;i<=n;i++){f[i]=1;
- for(j=1;j<=i-1;j++)
- if(f[j]+1>f[i] && a[j]>=a[i])f[i]=f[j]+1;
- }
- max1=0;
- for(i=1;i<=n;i++)if(f[i]>max1)max1=f[i];
- cout<<max1-1<<endl;
- f[1]=1;
- for(i=2;i<=n;i++){f[i]=1;
- for(j=1;j<=i-1;j++)
- if(f[j]+1>f[i] && a[j]<a[i])f[i]=f[j]+1;
- }
- max1=0;
- for(i=1;i<=n;i++)if(f[i]>max1)max1=f[i];
- cout<<max1;
- // cout<<f[n];
- return 0;
- }
- //O(nlogn)的代码，详情见鄙人博客的文章《单调队列优化LIS》
- #include <iostream>
- using namespace std;
- #include <cstdio>
- const int MaxN=100001;
- int n,i,top=0,x,stack[MaxN];
- int main(){
- cin>>n;
- stack[top]=-1;
- for(i=1;i<=n;i++){
- cin>>x;
- if(x>stack[top]){stack[++top]=x;}
- else
- {
- int low=0,high=top,mid;
- while(low<high){
- mid=(low+high)>>1;
- if(x>stack[mid])
- low=mid+1;
- else
- high=mid-1;
- }
- stack[low]=x;
- }
- }
- cout<<top;
- return 0;
- }
1.2.1 序列型动态规划例题——《线段覆盖2》（线段覆盖三部曲第二部）
数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。
n<=1000
第一行一个整数n，表示有多少条线段。
接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。
输出能够获得的最大价值
3
1 2 1
2 3 2
1 3 4
4
数据范围
对于40%的数据，n≤10；
对于100%的数据，n≤1000；
0<=ai,bi<=1000000
0<=ci<=1000000
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=1001;
- struct line{
- int L,R,val;
- friend bool operator< (line a,line b){return a.R<b.R;}//重载运算符来排序
- }a[MaxN];
- int f[MaxN],n,i,j;
- //f(i)表示前i条线段任意选择且必选择第i条线段能获得的最大值
- int main(){
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- scanf("%d%d%d",&a[i].L,&a[i].R,&a[i].val);
- sort(a+1,a+n+1);
- for(i=1;i<=n;i++)f[i]=a[i].val;
- for(i=2;i<=n;i++){
- for(j=1;j<i;j++)
- if(a[j].R<=a[i].L && f[j]+a[i].val>f[i])f[i]=a[i].val+f[j];
- if(f[i]>f[0])f[0]=f[i];
- }
- cout<<f[0];
- return 0;
- }
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
第一行一个整数n（n<=100）
第二行n个整数w1,w2...wn (wi <= 100)
一个整数表示最小合并代价
4
4 1 1 4
18
- #include <iostream>
- using namespace std;
- #include <cstdio>
- const int MaxN=101;
- int n,s[MaxN],f[MaxN][MaxN];
- int i,j,k,r;
- int main(){
- cin>>n;
- for(i=1;i<=n;i++){
- cin>>s[i];
- s[i]+=s[i-1];
- }
- for(r=2;r<=n;r++)
- for(i=1;i<=n-r+1;i++){
- j=i+r-1;
- f[i][j]=0x7fffffff;
- for(k=i;k<j;k++)
- f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
- }
- cout<<f[1][n];
- return 0;
- }
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)
(3，5) (5，10)
(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N<
span>时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。
4
2 3 5 10
710
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=205;//n<=100,这里拉两倍
- int f[MaxN][MaxN];//f(i,j)表示[i,j]这段区间的最优值(将最后一个点放入前面)
- int a[MaxN];
- int n;
- int main(){
- int i,j,k,r;
- cin>>n;
- for(i=1;i<=n;i++)
- {
- cin>>a[i];
- a[i+n]=a[i];
- }
- for(j=2;j<(n<<1);j++)
- for(i=j-1;i>0 && j-i<n;i--)
- for(k=i;k<j;k++)
- f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
- int MAX=0;
- for(i=1;i<=n;i++)
- MAX=max(MAX,f[i][i+n-1]);
- cout<<MAX;
- return 0;
- }
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
1) 3*12=36
2) 31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
程序的输入共有两行：
第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
第二行是一个长度为N的数字串。
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
4 2
1231
62
【分析】
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- typedef long long big;
- string s;
- int n,k;
- big f[41][7];//f(i,j)表示s中前i个数插入j个乘号所能得到的最大值
- big merge(int l,int r){
- big num=0;
- for(;l<=r;l++)num=num*10+s[l]-'0';
- return num;
- }
- int main(){
- cin>>n>>k;
- cin>>s;
- int i,j,ak;
- for(i=0;i<n;i++)f[i][0]=merge(0,i);
- for(i=1;i<n;i++)
- for(j=1;j<=k;j++)
- for(ak=0;ak<i;ak++)
- f[i][j]=max(f[i][j],f[ak][j-1]*merge(ak+1,i));
- cout<<f[n-1][k];
- return 0;
- }
将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的分法。
输入：n，k (6<n<=200，2<=k<=6)
输出：一个整数，即不同的分法。
7 3
4
{四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
【分析】
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=210;
- const int MaxM=7;
- int f[MaxN][MaxM];//f(i,j)表示数字i划分为j个数的和的方案数
- int n,m;
- int main(){
- cin>>n>>m;
- int i,j;
- f[0][0]=1;
- for(i=1;i<=n;i++)
- for(j=1;j<=m;j++)
- if(i>=j)f[i][j]+=f[i-j][j]+f[i-1][j-1];
- cout<<f[n][m];
- return 0;
- }
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
2
4 -1
3
当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
4 2
4
3
-1
2
7
81
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <list>
- #include <deque>
- #include <string>
- using namespace std;
- const int MaxN=51;
- const int MaxM=10;
- const int oo=30001;
- int n,m,a[MaxN*2];//断环为链
- int fmax[MaxN*2][MaxN*2][MaxM];//f(i,j,k)表示将环中i~j划分k段对10求模后的最大乘积
- int fmin[MaxN*2][MaxN*2][MaxM];
- int p,sum[MaxN*2][MaxN*2];
- int MAX=-oo,MIN=oo;
- int main(){
- cin>>n>>m;
- int i,j,k;
- for(i=1;i<=n;i++){
- cin>>a[i];
- a[n+i]=a[i];
- }
- n<<=1;
- for(i=1;i<=n;i++)
- for(j=i;j<=n;j++){
- p=0;
- for(k=i;k<=j;k++)
- p+=a[k];
- p=p%10;
- if(p<0)p+=10;
- sum[i][j]=p;
- }
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- for(k=1;k<=m;k++)
- {
- fmax[i][j][k]=-oo;
- fmin[i][j][k]=oo;
- }
- for(i=1;i<=n;i++)
- for(j=i;j<=n;j++){
- fmax[i][j][1]=sum[i][j];
- fmin[i][j][1]=sum[i][j];
- }
- for(i=1;i<=n;i++)
- for(j=i;j<=n;j++)
- for(k=2;k<=m;k++)
- for(p=j-1;p>=i;p--)
- {
- fmin[i][j][k]=min(fmin[i][j][k],fmin[i][p][k-1]*sum[p+1][j]);
- fmax[i][j][k]=max(fmax[i][j][k],fmax[i][p][k-1]*sum[p+1][j]);
- }
- n>>=1;
- for(i=1;i<=n;i++)
- {
- MAX=max(MAX,fmax[i][i+n-1][m]);
- MIN=min(MIN,fmin[i][i+n-1][m]);
- }
- cout<<MIN<<endl<<MAX;
- return 0;
- }