A 签到题--前缀和

预处理出前缀和，[l,r]的和即为

#include <bits/stdc++.h>
using namespace std; 

#define sc scanf
#define N 100005
const int MOD = 1e9+7;
ll a[N];

int main()
{
    int n,k;
    sc("%d %d",&n,&k);
    register int m;register int i;
    for(i=1;i<=n;++i){
        sc("%d",&m);
        a[i]+=m+a[i-1];
    }
    int l,r;
    for(i=0;i<k;++i){
        sc("%d %d",&l,&r);
        printf("%lld\n", a[r]-a[l-1]);
    }
    return 0;
}

C ---dp

没想到DP，一开始裸做的----3个相邻取中间 或两边的最小值；两个相邻取两者最大的；考虑到
1 1 2 3 4 这种情况当把第二个1加1之后，后面的都要改，所以先预处理出改动这个1之后需要付出的总代价；但很无奈，一个用例被卡住了，死活没想出来错在哪------ = =

#include <bits/stdc++.h>
using namespace std;

#define sc scanf
#define N 200055
const int MOD = 1e9+7;
ll a[N];
ll b[N];
ll con[N]={0};
ll con2[N]={0};// 预处理受影响的代价
ll d[N],d2[N];// 记录跳过pos
int main()
{
    int n;
    sc("%d",&n);
    for(int i=0;i<n;++i){
        sc("%lld %lld",&a[i],&b[i]);
    }
    int cons=0;
    ll cost=0;
    for(int i=0;i<n;++i){
        if(a[i]==a[i+1]+1){
            cons++;cost+=b[i];
        }else{
            con[i]= cost+b[i];
            cost=0;
            cons=0;
        }
    }
    cost=0;cons=0;
    for(int i=n-1;i>0;--i){
        if(a[i]==a[i-1]+1){
            //cout<<a[i]<<" "<<a[i-1]<<endl;
            cons++;cost+=b[i];
        }else{
            con2[i]= cost+b[i];d2[i]=cons;
            //cout<<"!! "<<a[i]<<" "<<con2[i]<<endl;
            cost=0;
            cons=0;
        }
    }
    for(int i=0;i<n;++i) {
        b[i]=max(con2[i],con[i]);//cout<<b[i]<<endl;
        if(con2[i]>con[i]){
            d[i]=d2[i];
        }else d[i]=0;
    }
    ll ans=0;
    for(int i=0;i<n-1;++i){
        if(a[i]==a[i+1]){
            if(i<=n-3 && a[i+1]==a[i+2]){
                if(b[i+1]<b[i]+b[i+2]) ans+=b[i+1],a[i+1]++;
                else {
                    ans+=b[i]+b[i+2],a[i]++,a[i+2]++;
                    i+=d[i+2];
                    //cout<<"? "<<i+1<<endl;
                }
            }else{
                ans+=min(b[i],b[i+1]);
                if(b[i]<b[i+1]) a[i]++,i+=d[i];
                else a[i+1]++,i+=d[i+1];
               // cout<<"! "<<i+1<<endl;
            }
        }
    }
    printf("%lld",ans);

    return 0;
}

DP做法：

先想dfs，因为每个数最多只能加1次，无非加或不加，但是时间复杂度满足不了---
考虑dp
dp[i][2]表示，前i个数满足相邻不相同的情况下，第i个数是否+1的最小花费
考虑没有限制条件时：

这里如果前一个数+1等于这个数，则 dp[i][0]不可以从dp[i-1][1]转移而来
即如果前一个数+1不等于这个数 则有
其他限制条件同理

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
#define int long long
int a[N],b[N];
int dp[N][2];//第i个数是否+1的最小代价---0代表不加1 1代表加1，
signed main(){
    int n;long long ans=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i],&b[i]);
    }
    memset(dp,0x3f3f,sizeof(dp));
    dp[1][0]=0,dp[1][1]=b[1];
    for(int i=2;i<=n;++i){
        if(a[i]!=a[i-1]) dp[i][0]=min(dp[i][0],dp[i-1][0]);
        if(a[i]!=a[i-1]+1) dp[i][0]=min(dp[i][0],dp[i-1][1]);
        if(a[i]+1!=a[i-1]) dp[i][1]=min(dp[i][1],dp[i-1][0]+b[i]);
        if(a[i]+1!=a[i-1]+1) dp[i][1]=min(dp[i][1],dp[i-1][1]+b[i]);
    }
    printf("%lld",min(dp[n][0],dp[n][1]));
    return 0;
}

D

以x结尾的长度为l的非降数组有多少种
不多说了，打个表吧。。。找一下规律，即C(x+l-2,x-1)
预处理出所有的阶乘和逆元阶乘,因为T比较大

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1,MOD=911451407;
int num[N],gia[N],dp[11][11];
inline int C(int x,int y){
    int res=(1LL*num[x]*gia[y])%MOD;
    res=(1LL*res*gia[x-y])%MOD;
    return res;
}
int main(){
    num[0]=num[1]=gia[0]=gia[1]=1;
    for(int i=2;i<N;++i){
        num[i]=(1LL*num[i-1]*i)%MOD;
        gia[i]=(1LL*gia[MOD%i]*(MOD-MOD/i))%MOD;
    }
    for(int i=2;i<N;++i){
        gia[i]=(1LL*gia[i-1]*gia[i])%MOD;
    }
    int T;
    cin>>T;
    while(T--){
        int l,x;cin>>l>>x;
        printf("%d\n",C(x+l-2,x-1));
    }
    return 0;
}