NOIP提高组 1999 & 2000 题解合集(一)

【序言】话说我在学神奇算法的时候，基础应该也要巩固，于是打算提前把NOIP提高组的刷完。

具体的题目描述和提交我就在VIJOS上完成。

【1999.1】

描述

给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。

例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。

样例输入：共一行，两个整数，分表为N与M的值。

格式

输入格式

一行，分别为N,M。

输出格式

两行。

第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。

第二行为最大值。

如果有多解，输出字典序最大的一个。

样例1

样例输入1

3 2

样例输出1

1 3
MAX=7

限制

各个测试点1s

来源

NOIP1999

【分析】似乎很早很早以前做到过~那时候因为不太懂各种算法，就乱搞搞过去了。但是现在思维复杂起来了，时间效率考虑的太多，反而难以下手。开始想的是贪心，发现是有问题的。数据范围N+M<=10，那么我们果断爆搜。在爆搜的途中如何随时更新值？只能用背包了。1A。

【代码】

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=605; int n,m,Max,i,a[15],ans[15],f[maxn]; int dp(int x) { memset(f,63,sizeof(f)); f[0]=0;int i,j; for (i=1;i<=maxn;i++) { for (j=1;j<=x;j++) if (i-a[j]>=0) f[i]=min(f[i-a[j]]+1,f[i]); if (f[i]>n) break; } return i-1; } void dfs(int step) { int now=dp(step); if (step==m) { if (now>Max) Max=now,memcpy(ans,a,sizeof(a)); return; } for (int i=now+1;i>a[step];i--) { a[step+1]=i; dfs(step+1); } } int main() { scanf("%d%d",&n,&m); a[1]=1;Max=0; dfs(1); for (i=1;i<=m;i++) printf("%d ",ans[i]); printf("\nMAX=%d",Max); return 0; }
    
   
  

【1999.2】

描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、出发点每升汽油价格p和沿途油站数n，油站i离出发点的距离d[i]、每升汽油价格p[i]。

计算结果四舍五入至小数点后两位。

如果无法到达目的地，则输出-1。

格式

输入格式

输入共n+1行，第一行为d1,c,d2,p,n，以下n行，每行两个数据，分别表示该油站距出发点的距离d[i]和该油站每升汽油的价格p[i]。两个数据之间用一个空格隔开。

输出格式

1 <= n <= 100

样例1

样例输入1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

样例输出1

26.95

限制

1s

提示

0<=n<=100

【分析】开始还以为是DP，仔细一想是贪心。因为细节没处理好，后来还下载数据调试= =。

策略：主要是采用搜索的框架（但是其实不是，每层只有一个点在操作）设当前到达的点是K。

①对于K能到的点中，找到第一个油费比K小的点P。若能找到，跳到②；否则跳到⑤。

②加上刚好去P的油，累加答案，并来到P这个状态。跳到①。

③说明在能到达的点中，K的油费最小。跳到④。

④判断K能否直接到达终点，若能累加答案并退出，否则跳到⑤。

⑤找到K能到达的点中油费最小的点，同时加满油驶向P。若已经没有点了，输出-1，否则跳到①。

但是很遗憾，还有一个小的问题：我们还要记录一下当前所剩的油量Q。以上过程都要涉及Q。

【代码】

#include
  
   
using namespace std;
double dis,c,speed,cost[105],X,COST,x[105],ans;
int N,i,n;
bool flag;
void walk(int k,double now)
{
  if (x[k]+speed*c
   
    =x[i];i++) if (cost[i]
    
     =need) walk(i,now-need); else ans+=(need-now)*cost[k],walk(i,0); return; } if (x[k]+speed*c>=dis) { flag=1; double need=(dis-x[k])/speed; if (now
     
      =x[i];i++) if (cost[i]
       
       
 
       
1999的其它两题就不必说了吧~~~
 
       
【2000.1】
 
       
 
       
 背景
 
       
JerryZhou同学经常改编习题给自己做。
 
       
这天，他又改编了一题。。。。。
 
       
 描述
 
       
设有N*N的方格图，我们将其中的某些方格填入正整数，
 而其他的方格中放入0。
 
       
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
 
       
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
 此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
 
       
 格式
 
       
输入格式
 
       
第一行:N (4<=N<=20)
 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0
 
       
输出格式
 
       
一行，表示最大的总和。
 
       
 样例1
 
       
样例输入1 
 
       
 
        
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
 
       
 
       
样例输出1 
 
       
 
        
39
 
       
 
       
 限制
 
       
各个测试点1s
 
       
 提示
 
       
多进程DP
 
       
【分析】其实原题是二取方格数，不过这样更加可以练练手。DP的方法应该很熟练了，我就写了些网络流。太高兴了，建图自己就YY出来了。设超级源点S，与左上角连一条费用为0，流量为3的边；设超级汇点T，与右下角连一条同样的边。能到达的两点连一条流量为INF，费用为0的边。然后把每个点拆成两个，连一条流量为INF，费用为0的边和一条流量为1，费用为权值的边。流量的意义是路径，费用的意义是价值。然后跑一遍最大费用最大流。
 
       
【代码】
 
       
 
       
#include
        
         
#include
         
           #include
          
            #define N 45 #define V 1005 #define M 80005 #define INF 2139062144 using namespace std; struct arr{int s,w,go,next;}a[M]; bool flag[V]; int f[V],q[M],pre[V],num[N][N][2],map[N][N],end[V]; int S,T,n,i,j,cnt,ans; bool spfa() { int h=0,t=1; memset(f,128,sizeof(f)); memset(flag,0,sizeof(flag)); f[S]=0;q[1]=S;flag[S]=true; while (h
           
            f[go]) { f[go]=f[now]+a[i].w;pre[go]=i; if (!flag[go]) { flag[go]=true;t++;q[t]=go; } } } flag[now]=false; } if (f[T]==-INF) return 0;return 1; } void cost() { int sum=INF; for (int i=pre[T];i;i=pre[a[i^1].go]) { sum=min(sum,a[