51nod——1402最大值、2479小b分糖果 （套路）

　　1402最大值：正向从1到n，如果没有限制，就依次递增1，如果有限制，就取那个限制和递增到这的最小值。这样保证1和每个限制点后面都是符合题意的递增，但是限制点前面这个位置可能会有落差（之前递增多了）。不过我们再反向来一遍，再使每一个限制点前面都是符合题意的递增，每个位置取反向这个过程和正向扫过的最小值。再对全局取max。

　　2479小b分糖果：正向从1到n，如果相邻且评分更高，就递增1，反向从n到1如果相邻且评分更高，就取后面位置递增1和正向扫过的最大值（前面的糖果已经是最少的了，不能减了）。再对全局求和。

1042：

 #include <bits/stdc++.h>

 using namespace std;

 #define maxn 100050

 int s[maxn], ans1[maxn],ans2[maxn];

 int main() {

     std::ios::sync_with_stdio ();

     cin.tie ();

     int t; cin >> t;

     while (t--) {

         int n, m; cin >> n >> m;

         memset (s, -, sizeof (s));

         memset (ans1, , sizeof (ans1));

         memset (ans2, , sizeof (ans2));

         for (int i = ; i < m; i++) {

             int id, x; cin >>id>>x ; s[id]=x;

         }

         for (int i = ; i <= n; i++) {

             ans1[i]=ans1[i-]+;

             if(s[i]!=-) ans1[i]=min(ans1[i],s[i]);

         }

         ans2[n]=ans1[n];

         for(int i = n - ; i > ; i--){

             ans2[i]=ans2[i+]+;

             if(s[i]!=-) ans2[i]=min(ans2[i],s[i]);

         }

         int maxx=;

         for(int i=;i<=n;i++)

             maxx=max(maxx,min(ans1[i],ans2[i]));

         cout<<maxx<<endl;

     }

     return ;

 }

2479：

 ///这题碰见两次了

 #include <bits/stdc++.h>

 using namespace std;

 #define maxn 50050

 int num[maxn],a[maxn];

 int main(){

     std::ios::sync_with_stdio();

     cin.tie();

     int n; cin>>n;

     long long ans=;

     for(int i=;i<n;i++) cin>>a[i];

     fill(num,num+n,);

     for(int i=;i<n;i++)

         if(a[i]>a[i-]) num[i]=num[i-]+;

     for(int i=n-;i>=;i--)

         if(a[i]>a[i+]) num[i]=max(num[i],num[i+]+);

     for(int i=;i<n;i++) ans+=num[i];

     cout<<ans<<endl;

     return ;

 }

51nod——1402最大值、2479小b分糖果 （套路）的相关教程结束。