Codeforces 1420 E. Battle Lemmings —— 暴力DP，想法

This way

題意：

給你n個數，如果有一對0之間有至少一個1，那麼這對0記錄答案，問你可以将1左右移動的話，移動最多i步的時候，答案是多少。

題解：

首先可以确定的就是将這個數組按照1為分隔劃分成多段，然後每段的貢獻就是（段内0數量）*（段外0數量），加起來除二就行了。

設段的數量是m，b[i]表示第i段的0數量

那麼答案其實就是 ( ∑ i = 1 m ( b [ i ] ∑ j = 1 m b [ i ] ) − ∑ i = 1 m ( b [ i ] ∗ b [ i ] ) ) / 2 (\sum\limits_{i=1}^{m}(b[i]\sum\limits_{j=1}^{m}b[i])-\sum\limits_{i=1}^{m}(b[i]*b[i]))/2 (i=1∑m​(b[i]j=1∑m​b[i])−i=1∑m​(b[i]∗b[i]))/2

首先前半段其實就相當于所有0的數量的平方，那麼我們DP隻需要求出後半段的最小值即可。

dp[i][j][k]表示到了第i個1，前面有j個0，走了k步的時候的 ∑ x = 1 i ( b [ x ] ∗ b [ x ] ) \sum\limits_{x=1}^{i}(b[x]*b[x]) x=1∑i​(b[x]∗b[x])最小值

轉移就是暴力枚舉下一個位置的0的數量

#include<bits/stdc++.h>
using namespace std;
const int N=85;
int dp[N][N][N*N],a[N],s[N];
int main()
{
    int n,m=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i])m++;
        else s[m]++;
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=m;i++)s[i]+=s[i-1];
    for(int i=0;i<m;i++){
        for(int j=0;j<=s[m];j++){
            for(int k=0;k<=n*(n-1)/2;k++){
                if(dp[i][j][k]==-1)continue;
                for(int l=j;l<=s[m];l++){
                    int step=k+abs(l-s[i+1]);
                    if(step>n*(n-1)/2)continue;
                    if(dp[i+1][l][step]==-1)dp[i+1][l][step]=dp[i][j][k]+(l-j)*(l-j);
                    else dp[i+1][l][step]=min(dp[i+1][l][step],dp[i][j][k]+(l-j)*(l-j));
                }
            }
        }
    }
    int mi=1e9;
    for(int i=0;i<=n*(n-1)/2;i++){
        if(dp[m][s[m]][i]!=-1)
            mi=min(mi,dp[m][s[m]][i]);
        printf("%d%c",(s[m]*s[m]-mi)/2," \n"[i==n*(n-1)/2]);
    }
    return 0;
}