被A弄的有点红温了，这次题解就随便写写吧

A

一眼DP 因为最多挖掉两个空格 但是只有64分

调了快一小时的DP都没出答案，有人和我说，只考虑挖第一个或最后一个，或者挖前两个，最后两个，挖最前最后过了？？？？？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
char s[10050];
long long dp[10050][3];
void solve(int n)
{
    scanf("%s",s+1);
    if(n<3)
    {
        printf("0 0\n");
        return;
    }
    int len=strlen(s+1);
    len=n;
    for(int i=0;i<=n+5;i++)
    {
        _for(j,0,2)
        {
            dp[i][j]=1000000000;
        }
    }
    dp[0][0]=0;
    _for(i,1,len)
    {
        _for(j,1,2) dp[i][j]=dp[i-1][j-1];
        if(i>=3)
        {
            dp[i][0]=dp[i-3][0]+abs((int)s[i-2]-'P')+abs((int)s[i-1]-'D')+abs((int)s[i]-'D');
            _for(j,1,2)
            {
                dp[i][j]=min(dp[i][j],dp[i-3][j]+abs((int)s[i-2]-'P')+abs((int)s[i-1]-'D')+abs((int)s[i]-'D'));
            }
        }
    } 
    printf("%d %lld\n",len/3,dp[len][len%3]);
}
int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        solve(n);
    }
}
/*
6
ADDPBB
6
ADDPBB
7
ABCDEFG
7
ABCDEFG
7
ABCDEFG
6
ADDPBB
7
ABCDEFG

*/

B

由于当(a[i]==a[i+1])时，合法区间的左端点一定≥l，因此一边维护目前所有合法区间的和，一边加给更新答案即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
#define MAXN 1000050
const int mod=10000007;
int arr[MAXN];
int main(void)
{
    int n;
    scanf("%d",&n);
    int ans=0;
    int cnt=0;
    int flag=0;
    _for(i,1,n) scanf("%d",&arr[i]);
    _for(i,1,n)
    {
        if(i==1||arr[i]==arr[i-1])
        {
            cnt=0;
            flag=0;
        }
        else
        {
            ++flag;
            cnt=(cnt)+(1ll*arr[i]*flag%mod)+arr[i-1];
            cnt%=mod;
            ans+=cnt;
            ans%=mod;
        }
        // printf("%d %d\n",cnt,ans);
    }
    printf("%d",ans);
}

C

枚举第一段，计算答案并且维护即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define MAXN 1050
#define pii pair<int,int>
int n;
int arr[MAXN];
pii judge(int len)
{
    int req=0;
    int wid=len;
    _for(i,1,len)
    {
        req+=arr[i];
    }
    int need,cnt;
    need=req,cnt=0;
    _for(i,len+1,n)
    {
        need-=arr[i];
        ++cnt;
        if(need<0)
        {
            return pii(n+1,-1);
        }
        if(need==0)
        {
            need=req;
            wid=max(wid,cnt);
            cnt=0;
        }
    }
    if(need!=req)
    {
        return pii(n+1,-1);
    }
    return pii(wid,req);
}
int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        _for(i,1,n) scanf("%d",&arr[i]);
        pii ans=pii(n+1,-1);
        _for(i,1,n)
        {
            ans=min(ans,judge(i));
        }
        printf("%d %d\n",ans.first,ans.second);
    }
}

D

做了个猜测，掰掉的巧克力要么取其中一块分，要么取其中一块的全部，用另一块分，由于时间紧张，没有去做数学证明，但是感觉比较合理，然后进行O(n^4)的DP即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define MAXN 55

int dp[MAXN][MAXN][MAXN];
void solve(int n,int m,int k)
{
    // printf("solve(%d %d %d)\n",n,m,k);
    dp[n][m][k]=998244353;
    if(n*m==k||k==0)
    {
        dp[n][m][k]=0;
        return;
    }
    if(n==0||m==0)
    {
        dp[n][m][k]=-1;
        return;
    }
    int cost;
    for(int i=1;i<n;i++)
    {
        cost=m*m;
        
        if(dp[n-i][m][k]!=-1) dp[n][m][k]=min(dp[n][m][k],dp[n-i][m][k]+cost);
        if(k-m*i>=0&&dp[n-i][m][k-m*i]!=-1) dp[n][m][k]=min(dp[n][m][k],dp[n-i][m][k-m*i]+cost);
        // printf("%d of n: %d\n",i,dp[n][m][k]);
    }
    for(int i=1;i<m;i++)
    {
        cost=n*n;
        if(dp[n][m-i][k]!=-1) dp[n][m][k]=min(dp[n][m][k],dp[n][m-i][k]+cost);
        if(k-n*i>=0&&dp[n][m-i][k-n*i]!=-1) dp[n][m][k]=min(dp[n][m][k],dp[n][m-i][k-n*i]+cost);
        // printf("%d of m: %d\n",i,dp[n][m][k]);
    }
    if(dp[n][m][k]==998244353) dp[n][m][k]=-1;
}
int main(void)
{
    _for(i,0,50) _for(j,0,50) _for(k,0,50) solve(i,j,k);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",dp[x][y][z]);
    }
}