Codeforces 1637 D. yet another minimization problem - Mathematics, DP

This way

The question ：

Give you a length of n Of a Array and b Array , You can choose one location at a time i, In exchange for a[i],b[i]. In the end, make $\sum _{i=1}^n\sum _{j=i+1}^n(a[i]+a[j]{)}^2+\sum _{i=1}^n\sum _{j=i+1}^n(b[i]+b[j]{)}^2$ Minimum .
What is the minimum value .

Answer key ：

This is a 1800？ I can't even think of it …
It seems that the problem of this formula has not been encountered for some time , I didn't even think about that .

It's almost such a process , So at the end of the formula a and b We already know the sum of the squares of , So what we are looking for is the smallest of the last two items .
hypothesis a And for x, that b The sum of is the sum of all the numbers -x Chant . See, for all a Is it possible that
dp[i][j] It means No i When we count ,a And for j The possibility of
So there are two cases of state transition ：

				if(j>=a[i])dp[1-i%2][j]|=dp[i%2][j-a[i]];
                if(j>=b[i])dp[1-i%2][j]|=dp[i%2][j-b[i]];

#include<bits/stdc++.h>
using namespace std;
const int N=105;
bool dp[2][N*N];
int a[N],b[N];
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--){
    
        int n,ans=0,r=0,sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i]*a[i]*(n-2),sum+=a[i];
        for(int i=1;i<=n;i++)scanf("%d",&b[i]),ans+=b[i]*b[i]*(n-2),sum+=b[i];
        memset(dp[1],0,sizeof dp[1]);
        dp[1][0]=1;
        for(int i=1;i<=n;i++){
    
            r+=max(a[i],b[i]);
            memset(dp[1-i%2],0,sizeof dp[1-i%2]);
            for(int j=r;j>=min(a[i],b[i]);j--){
    
                if(j>=a[i])dp[1-i%2][j]|=dp[i%2][j-a[i]];
                if(j>=b[i])dp[1-i%2][j]|=dp[i%2][j-b[i]];
            }

        }
        int mi=1e9;
        for(int i=0;i<=r;i++)
            if(dp[1-n%2][i])
                mi=min(mi,i*i+(sum-i)*(sum-i));
        printf("%d\n",ans+mi);
    }
    return 0;
}