codeforces #321 DIV2

A题：

链接：http://codeforces.com/contest/580/problem/A

dp，最长连续不上升子序列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 const int maxn=100010;
 9 int a[maxn],dp[maxn];
10 int main()
11 {
12     int n;
13     while(cin>>n)
14     {
15         for(int i=0;i<n;i++)
16             scanf("%d",&a[i]);
17         memset(dp,0,sizeof(dp));
18         dp[0]=1;
19         for(int i=1;i<n;i++)
20         {
21             if(a[i-1]<=a[i])
22                 dp[i]=dp[i-1]+1;
23                 else
24                     dp[i]=1;
25         }
26         int mx=0;
27         for(int i=0;i<n;i++)
28             if(dp[i]>mx)
29             mx=dp[i];
30         cout<<mx<<endl;
31     }
32     return 0;
33 }

View Code

B题：

链接：http://codeforces.com/contest/580/problem/B

贪心，先按照m升序排序，然后找出符合条件且最大的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<algorithm>
 8 using namespace std;
 9 const int maxn=100010;
10 typedef struct
11 {
12     long long m,s;
13 }point;
14 point p[maxn];
15 bool cmp(point a,point b)
16 {
17     return a.m<b.m;
18 }
19 int main()
20 {
21     long long n,d;
22     while(cin>>n>>d)
23     {
24         for(int i=0;i<n;i++)
25             cin>>p[i].m>>p[i].s;
26         sort(p,p+n,cmp);
27         long long ans=0;
28         long long cnt=0;
29         int j=0;
30         for(int i=0;i<n;i++)
31         {
32             cnt+=p[i].s;
33             while(p[i].m-p[j].m>=d)
34             {
35                 cnt-=p[j].s;
36                 j++;
37             }
38             ans=max(ans,cnt);
39         }
40         cout<<ans<<endl;
41     }
42     return 0;
43 }

View Code

C、D、E赛场上没有搞出来，抽时间来补上