这次考试，我考得不太好，就在这里整理一下
1.第一题是一个变相的线段树，我居然没看是要查询区间最小值，就把查询和修改都加到了单点，就超时了，只得了40分
2.第二题是原题“跳石头”，还是拿到了满分
3.“花匠”，我想了一个O(n^2)的DP做法，时间不够了，就没打完优化，有两个点超了时，得了80分。
2012年NOIP全国联赛提高组
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要
向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份
订单，每份订单用三个正整数描述，分别为dj, sj, tj，表示某租借者需要从第sj天到第tj天租
借教室（包括第sj天和第tj天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提
供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教
室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申
请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改
订单。
第一行包含两个正整数n, m，表示天数和订单的数量。
提高组 day2
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj, sj, tj，表示租借的数量，租借开始、结束分别在
第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
如果所有订单均可满足，则输出只有一行，包含一个整数 0。否则（订单无法完全满足）
输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
-1
2
【输入输出样例说明】
classroom.out
-1
2
第 1 份订单满足后，4 天剩余的教室数分别为 0，3，2，3。第 2 份订单要求第 2 天到
第 4 天每天提供 3 个教室，而第 3 天剩余的教室数为 2，因此无法满足。分配停止，通知第
2 个申请人修改订单。
【数据范围】
对于 10%的数据，有1 ≤ n, m ≤ 10；
对于 30%的数据，有1 ≤ n, m ≤ 1000；
对于 70%的数据，有1 ≤ n, m ≤ 105；
对于 100%的数据，有1 ≤ n, m ≤ 10^6, 0 ≤ ri, dj≤ 10^9, 1 ≤ sj≤ tj≤ n。
1 #define N 1000010 2 #include<iostream> 3 using namespace std; 4 #include<cstdio> 5 #include<cstring> 6 #define ll long long 7 struct Tree{ 8 int lazy,minn; 9 Tree() 10 {lazy=0;minn=(1<<31)-1;} 11 }tree[N*4]; 12 int d,tc[N]; 13 int n,m,s,t; 14 void input() 15 { 16 scanf("%d%d",&n,&m); 17 for(int i=1;i<=n;++i) 18 scanf("%d",&tc[i]); 19 } 20 void update(int k) 21 { 22 int lch=(k<<1),rch=((k<<1)+1); 23 tree[k].minn=min(tree[lch].minn,tree[rch].minn); 24 } 25 void build_tree(int k,int l,int r) 26 { 27 if(l==r) 28 { 29 int temp=tc[l]; 30 tree[k].minn=temp; 31 return; 32 } 33 int mid=(l+r)>>1,lch=(k<<1),rch=((k<<1)+1); 34 build_tree(lch,l,mid); 35 build_tree(rch,mid+1,r); 36 update(k); 37 } 38 void down(int k) 39 { 40 int lch=(k<<1),rch=((k<<1)+1); 41 ll lazy1=tree[k].lazy; 42 tree[lch].lazy+=lazy1;tree[lch].minn+=lazy1; 43 tree[rch].lazy+=lazy1;tree[rch].minn+=lazy1; 44 tree[k].lazy=0; 45 } 46 void add(int k,int l,int r,int x,int y,ll chan) 47 { 48 if(l==x&&y==r) 49 { 50 tree[k].minn+=chan; 51 tree[k].lazy+=chan; 52 return; 53 } 54 if(tree[k].lazy) 55 down(k); 56 int mid=(l+r)>>1,lch=(k<<1),rch=((k<<1)+1); 57 if(x<=mid) add(lch,l,mid,x,min(y,mid),chan); 58 if(y>mid) add(rch,mid+1,r,max(mid+1,x),y,chan); 59 update(k); 60 } 61 int main() 62 { 63 input(); 64 build_tree(1,1,n); 65 for(int i=1;i<=m;++i) 66 { 67 scanf("%d%d%d",&d,&s,&t); 68 add(1,1,n,s,t,-d); 69 if(tree[1].minn<0) 70 { 71 printf("-1\n%d",i); 72 return 0; 73 } 74 } 75 printf("0"); 76 return 0; 77 }
2013年NOIP全国联赛提高组
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h_1, h_2, … , h_n。设当一部分花被移走后，剩下的花的高度依次为g_1, g_2, … , g_m，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的1<i<m/2，g_2i > g_2i-1，且g_2i > g_2i+1；
条件 B：对于所有的1<i<m/2，g_2i < g_2i-1，且g_2i < g_2i+1。
注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
输入的第一行包含一个整数 n，表示开始时花的株数。
第二行包含 n 个整数，依次为h_1, h_2,… , h_n，表示每株花的高度。
输出一行，包含一个整数 m，表示最多能留在原地的花的株数。
5
5 3 2 1 2
3
对于 20%的数据，n ≤ 10；
对于 30%的数据，n ≤ 25；
对于 70%的数据，n ≤ 1000，0 ≤ h_i ≤ 1000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ h_i ≤ 1,000,000，所有的h_i随机生成，所有随机数服从某区间内的均匀分布。
DP超时代码：
1 #include<iostream> 2 using namespace std; 3 #include<cstdio> 4 #include<cstring> 5 #define N 100100 6 int n,high[N]; 7 int maxx=-1; 8 int dp[N][2]={0}; 9 int read() 10 { 11 int ans=0,ff=1;char s; 12 s=getchar(); 13 while(s<‘0‘||s>‘9‘) 14 { 15 if(s==‘-‘) ff=-1; 16 s=getchar(); 17 } 18 while(‘0‘<=s&&s<=‘9‘) 19 { 20 ans=ans*10+s-‘0‘; 21 s=getchar(); 22 } 23 return ans*ff; 24 } 25 void input() 26 { 27 n=read(); 28 for(int i=1;i<=n;++i) 29 high[i]=read(); 30 } 31 void DP() 32 { 33 memset(dp,0,sizeof(dp)); 34 dp[1][0]=1;dp[1][1]=1; 35 maxx=1; 36 for(int i=2;i<=n;++i) 37 { 38 dp[i][1]=dp[i][0]=1; 39 for(int j=1;j<=i-1;++j) 40 { 41 if(high[i]>high[j]) 42 dp[i][1]=max(dp[i][1],dp[j][0]+1); 43 if(high[i]<high[j]) 44 dp[i][0]=max(dp[i][0],dp[j][1]+1); 45 } 46 maxx=max(maxx,max(dp[i][1],dp[i][0])); 47 } 48 } 49 int main() 50 { 51 input(); 52 DP(); 53 printf("%d\n",maxx); 54 return 0; 55 }
非常简单的正解：
1 /*注意：以后注意这里的DP做法：完全可以用线性DP做 2 这里的dp[i][0],或者dp[i][1]虽然不表示以i-1结尾的序列，但是状态转移的仅仅根据i-1与i的关系，就可以确定出怎么向下转移了*/ 3 #define N 100010 4 #include<iostream> 5 using namespace std; 6 #include<cstdio> 7 int high[N],f[N][2]; 8 int n; 9 int main() 10 { 11 scanf("%d",&n); 12 for(int i=1;i<=n;++i) 13 scanf("%d",&high[i]); 14 f[1][1]=1;f[1][0]=1; 15 for(int i=2;i<=n;++i) 16 { 17 f[i][0]=f[i-1][0];/*处理一直序列相等的情况，先赋值就好*/ 18 if(high[i]<high[i-1]) 19 f[i][0]=max(f[i-1][0],f[i-1][1]+1); 20 /*我们这里假设前面有一个最长的序列k，结尾是i-1的下降，那么既然high[i]<high[i-1]，则把这个序列·的最后一个也就是i-1换为i也是可以的，再看f[i-1][1]+1，我们从假设可知，i-1是不在这个k-1长的上升序列的，i-1不是最后一个是因为i-1的高度，小于倒数第二个，所以既然high[i]<high[i-1]，那么这个上升序列也可以接上第i个，其他的情况不解释，同理*/ 21 f[i][1]=f[i-1][1]; 22 if(high[i]>high[i-1]) 23 f[i][1]=max(f[i-1][1],f[i-1][0]+1); 24 } 25 cout<<max(f[n][0],f[n][1])<<endl; 26 return 0; 27 }
原文：http://www.cnblogs.com/c1299401227/p/5554696.html