思路： d p dp dp。
不会写，参考别人的代码，
a n s = n ( n − 1 ) 2 − c n t 1 ( c n t 1 − 1 ) 2 − c n t 1 ( n − c n t 1 ) − ∑ c o n t i n u o u s _ p a i r ( 0 , 0 ) ans=\dfrac{n(n-1)}{2}-\dfrac{cnt_1(cnt_1-1)}{2}-cnt_1(n-cnt_1)-\sum continuous\_pair(0,0) ans=2n(n−1)−2cnt1(cnt1−1)−cnt1(n−cnt1)−∑continuous_pair(0,0)
令 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示安排好前 i i i个1，且第 i i i个1位于位置 j j j，使用 k k k次操作后的最小 0 0 0对。
对于一个长为 x x x的连续 0 0 0对，贡献为： x ( x − 1 ) 2 \dfrac{x(x-1)}{2} 2x(x−1)
先找到所有 1 1 1的位置 b [ i ] b[i] b[i](第 i i i个1的位置)，然后初始化 d p [ i ] [ b [ i ] ] [ 0 ] dp[i][b[i]][0] dp[i][b[i]][0]
然后跑 d p dp dp，最后注意要加上末尾的最后一段0的贡献。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=105,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int n,c,sz,a[N],b[N]; ll dp[82][82][82*82]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]),c+=a[i]; if(a[i]) b[++sz]=i; } ll ans=n*(n-1)/2-c*(c-1)/2-c*(n-c); mst(dp,0x3f); ll tmp=0; for(int i=0;i<=sz;i++){ if(i) tmp+=max(0,(b[i]-b[i-1]-1)*(b[i]-b[i-1]-2)/2); dp[i][b[i]][0]=tmp; } for(int i=1;i<=sz;i++) for(int j=1;j<=n;j++) for(int k=0;k<j;k++) for(int l=0;l<=n*(n-1)/2;l++) dp[i][j][abs(j-b[i])+l]=min(dp[i][j][abs(j-b[i])+l],dp[i-1][k][l]+max(0,(j-k-1)*(j-k-2)/2)); ll mn=1e18; for(int i=0;i<=n*(n-1)/2;i++){ for(int j=1;j<=n;j++){ mn=min(mn,dp[sz][j][i]+max(0,(n-j)*(n-j-1)/2)); } if(!sz) mn=ans; printf("%lld ",ans-mn); } return 0; }