ac代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef pair<int,int> pii;
typedef long long ll;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int N=105,M=N*N;
int a[N];
int b[N];
bool dp[N][M];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int cal=0;//平方和
        int sum=0;
        int res=0;
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            cal+=a[i]*a[i];
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            sum+=b[i];
            cal+=b[i]*b[i];
        }
        if(n==1)
        {
            puts("0");
            continue;
        }

        res+=(n-2)*cal+sum*sum;
        memset(dp,false,sizeof dp);
        dp[0][0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=a[i];j<=sum;j++)
            {
                if(dp[i-1][j-a[i]])
                dp[i][j]=true;
            }
            for(int j=b[i];j<=sum;j++)
            {
                if(dp[i-1][j-b[i]])
                dp[i][j]=true;
            }
        }

        int ans=0;
        for(int i=0;i<=sum;i++)
        {
            if(dp[n][i]&&dp[n][sum-i])
            {
                ans=max(ans,i*(sum-i));
            }
        }
        printf("%d\n",res-2*ans);
    }
}