第三届山东ACM省赛 Fruit Ninja I

 http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2412

题意：一个切水果游戏。每秒出现一些水果，它们都在一条线上，有好水果和坏水果，好的可以加分，坏的减分，每次连续切好水果三个以上可以分数加倍。每秒只能切一次，每切一次要间隔m秒。问最多得多少分。

暴力+dp 开始的时候没想到，没什么头绪，因为每一次需要间隔一定的时间，但是没考虑到每个时间点t内的最大值是可求得，这样直接DP就好了。。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 10010
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
using namespace std;
struct Stru{
  int time;
  int x;
  int mm;
}pos[MAX];
int arr[MAX];
int dp[MAX];

bool cmp(Stru a,Stru b){
  if(a.time!=b.time) return a.time<b.time;
  return a.x<b.x;
}

int main()
{
   int T;
   scanf("%d",&T);
   int n,m,temp,Case=1;
   while(T--){
      scanf("%d%d",&n,&m);
      for(int i=0;i<n;i++){
        scanf("%d%d%d",&pos[i].time,&temp,&pos[i].x);
        pos[i].mm = ( temp == 0 ? 1 : -1);
      }
      memset(arr,0,sizeof(arr));
      sort(pos,pos+n,cmp);
      
      
      int start=pos[0].time,sum=0,seque=0,mmax=0;///start:当前正在判断的时间标志
                                                 ///sum:在start秒里到当前位置能获得的最大的分数
                                                 ///     注意！如果seque统计需要加倍时在seque清0之前是没有Double分数的）
                                                 ///seque:连续的个数（用来最后统计Double分数的）
                                                 ///mmax:当前秒获得的最大分数
                                                 
      ///该部分统计分数的精髓：http://blog.csdn.net/u014665013/article/details/50094365
      for(int i=0;i<n;i++){ ///暴力求每个时间t能获得的最大分数(连续区间最大值)
        if(pos[i].time==start){
           if(pos[i].mm==-1){
              if(seque>=3) sum+=seque;
              seque=0;
           }
           else seque++;
           
           sum += pos[i].mm;
           if ( sum+(seque>=3?seque:0) > mmax)
              mmax = sum+(seque>=3?seque:0);
           else if (sum < 0)
              sum = 0;
        }
        else{
            arr[ pos[i-1].time ] = mmax;
            start=pos[i].time;
            sum=0,seque=0;
            if(pos[i].mm==1)
               sum=1,seque=1;
            mmax=sum;
        }
      }
      arr[pos[n-1].time]=mmax;

      dp[0]=0;
      for(int i=1;i<=pos[n-1].time;i++){  ///dp最大值 转移方程 dp[i]=dp[i-1],dp[i-m-1]+arr[i]
        if(i>m+1)
            dp[i]=max(dp[i-1],dp[i-m-1]+arr[i]);
        else
            dp[i]=max(dp[i-1],arr[i]);
      }
      printf("Case %d: %d
",Case++,dp[pos[n-1].time]);
   }
   return 0;
}