学步园

               题意:

                       有N(N<=10^6)个target排成一列(标号为1~N)..现在要选择一些target..并且告诉对于每个target..其得分的方式..对于选了第i个target得分

                            1、若其左右没有一个target被选择...得ai分

                            2、若其左右中有一个target被选择.,.得bi分

                            3、若其左右中无一个target被选择...得ci分

                       问能得到的最大分数...

               题解:

                       由于影响一个位置的取值分数仅与其右边和做边的点有关..所以可以用dp[i][x][y]代表扫到了第i个..第i个target是否选择了..第i-1个target是否选择了的最大值..

Program:

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <string.h>
#define oo 1000000007
#define MAXN 1000500
using namespace std;
int dp[2][2][2],a[MAXN],b[MAXN],c[MAXN];
int turn(int l,int x,int r)
{
       if (!l && !r) return a[x];
       if (l+r==1) return b[x];
       return c[x];
}
int main()
{
       int N,t,i,j,x,k,ans; 
       while (~scanf("%d",&N))
       {
               a[0]=b[0]=c[0]=0;
               for (i=1;i<=N;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
               c[1]=c[N]=-oo;
               if (N==1) b[1]=-oo;
               memset(dp[0],-0x3f,sizeof(dp[0]));
               dp[0][0][0]=0;
               k=ans=0;
               for (t=1;t<=N+1;t++)
               {
                       k=1-k;
                       memset(dp[k],-0x3f,sizeof(dp[k]));
                       for (x=0;x<2;x++)
                         for (i=0;i<2;i++)
                           for (j=0;j<2;j++)
                           {
                                  if (i) //别忘了...
                                       dp[k][i][j]=max(dp[k][i][j],dp[1-k][x][i]+turn(x,t-1,j));
                                    else
                                       dp[k][i][j]=max(dp[k][i][j],dp[1-k][x][i]);
                                  ans=max(ans,dp[k][i][j]);
                           }
               }
               printf("%d\n",ans);

       }
       return 0;
}