A:DZY Loves Sequences

一开始看错题了。。sad。

题目很简单，做法也很简单。DP一下就好了。

dp[i][0]:到当前位置，没有任何数改变，得到的长度。

dp[i][1]:到当前位置，改变了一个数，得到的长度

不过需要正向求一遍，然后反向求一遍。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define maxn 110000
int dp[maxn][3];
int num[maxn];
int a[maxn];
int n;
void dos(int maxx)
{
    memset(dp,0,sizeof(dp));
    memset(num,-1,sizeof(num));
    for(int i=n; i>=1; i--)
    {
        if(a[i]<a[i+1])
        {
            dp[i][0]=dp[i+1][0]+1;
        }
        else
        {
            dp[i][0]=1;
        }
        dp[i][1]=dp[i][0];
        num[i]=a[i];
        if(a[i]<num[i+1])
        {
            if(dp[i][1]<dp[i+1][1]+1)
            {
                dp[i][1]=dp[i+1][1]+1;
                num[i]=a[i];
            }
        }
        if(a[i]>=a[i+1])
        {
            if(dp[i][1]<dp[i+1][0]+1)
            {
                dp[i][1]=dp[i+1][0]+1;
                num[i]=a[i+1]-1;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
         //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;
        maxx=max(maxx,dp[i][0]);
        maxx=max(maxx,dp[i][1]);
    }
    cout<<maxx<<endl;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        memset(num,-1,sizeof(num));
        for(int i=1; i<=n; i++)
        {
            if(a[i]>a[i-1])
            {
                dp[i][0]=dp[i-1][0]+1;
            }
            else
            {
                dp[i][0]=1;
            }
            dp[i][1]=dp[i][0];
            num[i]=a[i];
            if(a[i]>num[i-1])
            {
                if(dp[i][1]<dp[i-1][1]+1)
                {
                    dp[i][1]=dp[i-1][1]+1;
                    num[i]=a[i];
                }
            }
            if(a[i]<=a[i-1])
            {
                if(dp[i][1]<dp[i-1][0]+1)
                {
                    dp[i][1]=dp[i-1][0]+1;
                    num[i]=a[i-1]+1;
                }
            }
        }
        int maxx=-1;
        for(int i=1; i<=n; i++)
        {
            // cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;
            maxx=max(maxx,dp[i][0]);
            maxx=max(maxx,dp[i][1]);
        }
        dos(maxx);
    }
    return 0;
}

我们可以发现选择一个横行，竖行的大小顺序不变，只是每一个竖行都下降了p。

所以我们可以枚举选择了x个横行，y个竖行。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 1100
#define LL __int64
int mp[maxn][maxn];
int hh[maxn];
int ll[maxn];
LL ph[1100000];
LL pl[1100000];
priority_queue<int>que;
int n,m,k,p;
void chu()
{
    ph[0]=pl[0]=0;
    while(!que.empty())que.pop();
    for(int i=1;i<=n;i++)
    {
        que.push(hh[i]);
    }
    for(int i=1;i<=k;i++)
    {
        int x=que.top();
        que.pop();
        ph[i]=ph[i-1]+(LL)x;
        x=x-p*m;
        que.push(x);
    }
    while(!que.empty())que.pop();
    for(int i=1;i<=m;i++)
    {
        que.push(ll[i]);
    }
    for(int i=1;i<=k;i++)
    {
        int x=que.top();
        que.pop();
        pl[i]=pl[i-1]+(LL)x;
        x=x-p*n;
        que.push(x);
    }
}
int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&k,&p))
    {
        memset(hh,0,sizeof(hh));
        memset(ll,0,sizeof(ll));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&mp[i][j]);
                hh[i]+=mp[i][j];
                ll[j]+=mp[i][j];
            }
        }
        chu();
        LL ans=pl[k];
        for(int i=1;i<=k;i++)
        {
            LL x=(LL)i*(LL)(k-i);
            x=(LL)x*(LL)p;
            ans=max(ans,pl[k-i]+ph[i]-x);
        }
        cout<<ans<<endl;
    }
    return 0;
}

主要是两个性质：

1,两个斐波那契数列相加依然是一个斐波那契数列。

2，根据斐波那契数列的前两项可以O（1）的时间内得出任意一个位置的斐波那契数，和任意长度的斐波那契数列的合。

剩下的东西就是简单的区间求和问题了。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define mem(a,b) (memset(a),b,sizeof(a))
#define lmin 1
#define rmax n
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now int l,int r,int rt
#define INF 99999999
#define LL __int64
#define mod 1000000009
#define eps 1e-6
#define zero(x) (fabs(x)<eps?0:x)
#define maxn 330000
LL sum[maxn<<2];
LL f1[maxn<<2];
LL f2[maxn<<2];
LL fib[maxn];
LL look(int a,int b,int n)
{
    if(n==1)return a;
    if(n==2)return b;
    return (a*fib[n-2]+b*fib[n-1])%mod;
}
LL suan(int a,int b,int n)
{
    if(n==1)return a;
    if(n==2)return (a+b)%mod;
    return ((look(a,b,n+2)-b)%mod+mod)%mod;
}
void push_up(int_now)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    sum[rt]=sum[rt]%mod;
}
void push_down(int_now)
{
    if(f1[rt]!=0)
    {
        LL ll,rr;
        ll=(l+r)/2-l+1;
        rr=r-(l+r)/2;
        LL x,y;
        x=f1[rt];
        y=f2[rt];
        f1[rt<<1]=(f1[rt<<1]+x)%mod;
        f2[rt<<1]=(f2[rt<<1]+y)%mod;
        sum[rt<<1]=(sum[rt<<1]+suan(x,y,ll))%mod;
        LL px,py;
        px=x;py=y;
        x=look(px,py,ll+1);
        y=look(px,py,ll+2);
        //cout<<x<<" "<<y<<" +"<<rr<<endl;
        f1[rt<<1|1]=(f1[rt<<1|1]+x)%mod;
        f2[rt<<1|1]=(f2[rt<<1|1]+y)%mod;
        sum[rt<<1|1]=(sum[rt<<1|1]+suan(x,y,rr))%mod;
        f1[rt]=f2[rt]=0;
    }
}
void creat(int_now)
{
    sum[rt]=f1[rt]=f2[rt]=0;
    if(l!=r)
    {
        creat(lson);
        creat(rson);
        push_up(now);
    }
    else
    {
        scanf("%I64d",&sum[rt]);
    }
}
void updata(int ll,int rr,int_now)
{
    if(ll>r||rr<l)return;
    if(ll<=l&&rr>=r)
    {
        f1[rt]+=fib[l-ll+1];
        f2[rt]+=fib[l-ll+2];
        sum[rt]+=suan(fib[l-ll+1],fib[l-ll+2],r-l+1);
        sum[rt]=(sum[rt]+mod)%mod;
        f1[rt]=f1[rt]%mod;
        f2[rt]=f2[rt]%mod;
        return;
    }
    push_down(now);
    updata(ll,rr,lson);
    updata(ll,rr,rson);
    push_up(now);
}
LL query(int ll,int rr,int_now)
{
    if(ll>r||rr<l)return 0;
   /// cout<<l<<"-"<<r<<" "<<sum[rt]<<endl;
    if(ll<=l&&rr>=r)return sum[rt];
    push_down(now);
    return (query(ll,rr,rson)+query(ll,rr,lson))%mod;
}
int main()
{
    fib[1]=1;fib[2]=1;
    for(int i=3;i<maxn;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
        fib[i]=fib[i]%mod;
    }
    int n,m,k,l,r;
    while(~scanf("%d%d",&n,&m))
    {
        creat(root);
        while(m--)
        {
            scanf("%d%d%d",&k,&l,&r);
            if(k==1)updata(l,r,root);
            else
            {
                printf("%I64d\n",query(l,r,root));
            }
        }
    }
    return 0;
}