zoj Candies 贪心

根据题目可知3K位置的数量是可以直接确定的，并且n-2-3*k的也可以确定。所以只要这两部分不重合，答案就是确定的，或者有额外的位置是原来就已知，也是确定的。答案不确定的情况下，容易知道，有%3==1位置是同时取到最大值的，mod3==2也是同时取到最大值的。所以可以分别求出这两部分的最大值，然后O(1)回答。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
const int maxn=1e5+9,inf=1e9;  
int a[maxn],sum[maxn];  
int max1[maxn],max2[maxn];  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    int n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        a[n+1]=a[0]=0;  
        for(int i=1;i<=n;i++)  
        scanf("%d",&a[i]);  
        for(int i=1;i<=n;i++)  
        scanf("%d",&sum[i]);  
  
        for(int i=3;i<=n;i+=3)  
        a[i]=sum[i-1]-(sum[i-2]-a[i-3]);  
  
        for(int i=n-2;i>=1;i-=3)  
        a[i]=sum[i+1]-(sum[i+2]-a[i+3]);  
  
        for(int i=1;i+2<=n;i++)  
        {  
            int tmp=0,txt,ss=0;  
            for(int j=0;j<=2;j++)  
            if(a[i+j]==-1) tmp++,txt=i+j;  
            else ss+=a[i+j];  
            if(tmp==1)  
            a[txt]=sum[i+1]-ss;  
        }  
  
        for(int i=n-2;i>=1;i--)  
        {  
            int tmp=0,txt,ss=0;  
            for(int j=0;j<=2;j++)  
            if(a[i+j]==-1) tmp++,txt=i+j;  
            else ss+=a[i+j];  
            if(tmp==1)  
            a[txt]=sum[i+1]-ss;  
        }  
  
        bool flag=true;  
        for(int i=1;i<=n;i++)  
        if(a[i]==-1) flag=false;  
  
        if(flag)  
        {  
            int m;  
            scanf("%d",&m);  
            for(int i=1,tmp;i<=m;i++)  
            {  
                scanf("%d",&tmp);  
                printf("%d\n",a[tmp+1]);  
            }  
        }  
        else  
        {  
            for(int i=1;i<=n;i++)  
            if(a[i]!=-1)  
            max1[i]=max2[i]=a[i];  
            else  
            max1[i]=max2[i]=-inf;  
  
            int min1=inf,min2=inf;  
            max1[1]=100000;  
            for(int i=1;i+2<=n;i++)  
            {  
                int tmp=0,txt,ss=0;  
                for(int j=0;j<=2;j++)  
                if(max1[i+j]==-inf) tmp++,txt=i+j;  
                else ss+=max1[i+j];  
                if(tmp==1)  
                {  
                    max1[txt]=sum[i+1]-ss;  
                    min1=min(min1,max1[txt]);  
                }  
            }  
  
            max2[2]=100000;  
            for(int i=1;i+2<=n;i++)  
            {  
                int tmp=0,txt,ss=0;  
                for(int j=0;j<=2;j++)  
                if(max2[i+j]==-inf) tmp++,txt=i+j;  
                else ss+=max2[i+j];  
                if(tmp==1)  
                {  
                    max2[txt]=sum[i+1]-ss;  
                    min2=min(min2,max2[txt]);  
                }  
            }  
  
            int m;  
            scanf("%d",&m);  
            for(int i=1,tmp;i<=m;i++)  
            {  
                scanf("%d",&tmp);  
                tmp++;  
                if(tmp%3==0)  
                printf("%d\n",a[tmp]);  
                else if(tmp%3==1)  
                printf("%d\n",max1[tmp]+min1);  
                else  
                printf("%d\n",max2[tmp]+min2);  
            }  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,