Codeforces gr19 D (think more about why the first-hand value range is 100, JLS yyds)

subject
The question : Given array a、b, You can exchange any number i Location a[i] and b[i], Make the formula in the following figure minimum .(n<=100,a[i]、b[i]<=100)

Ideas : We must simplify the formula first , Otherwise, I don't know what to do . After simplification, I found that I didn't care about the square term , Just focus on the minimum sum of squares of the sum of two arrays . Can pass dp Find out all the values that can be obtained by one of the arrays , You can find the minimum value .
Method 1: f[i][j]: Before use only i Number , Make and for j.true It means you can come up with . Because the maximum is 100, most 1e6. ( The first dimension can be optimized as 0、1)
Method 2: You might as well change the small numbers to a in , Big numbers are put in b in . adopt dp Find out through exchange ,a Array new sum , Record minimum . It can be used bitset maintain a Arrays are swapped to get new sums .
Time complexity : O(nmaxmax = 1e6), It can be used bitset Optimize ,emmm Feeling is 8 times ? But the explanation is 64 times , Don't know much about .
Code :
bitset

#include<bits/stdc++.h>
using namespace std;
const int MAXSUM = 100*100+10;
int n,m,k,T;
int fun(int x)
{
    
	return x * x ;
}
void solve()
{
    
    scanf("%d",&n);
    vector<int> a(n+1),b(n+1);
    long long ans = 0; int l = 0,r = 0; // and 
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),ans += fun(a[i]);
    for(int i=1;i<=n;++i) scanf("%d",&b[i]),ans += fun(b[i]);
    for(int i=1;i<=n;++i)
    {
    
    	if(a[i] > b[i]) swap(a[i],b[i]);
    	l += a[i];
    	r += b[i];
    }
    ans *= (n-2);
    int res = 1e9;
    bitset<MAXSUM> dp;
    dp[0] = 1;
    for(int i=1;i<=n;++i)
    {
    
    	dp |= (dp<<(b[i]-a[i]));
    }
    for(int i=0;i<=r-l;++i)
    {
    
    	if(dp[i])
    	res = min(res,fun(l+i)+fun(r-i));
    }
    ans += res;
    printf("%lld\n",ans);
}
signed main(void)
{
    
	scanf("%d",&T);
	while(T--)
	solve();
	return 0;
}

Ordinary dp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<complex>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<list>
#include<set>
#include<queue>
#include<stack>
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i<=b;++i) 
#define mem(a,x) memset(a,x,sizeof(a))
#define p_ priority_queue
// round()  rounding  ceil()  Rounding up  floor()  Rounding down 
// lower_bound(a.begin(),a.end(),tmp,greater<ll>())  First less than or equal to 
// #define int long long //QAQ
using namespace std;
typedef complex<double> CP;
typedef pair<int,int> PII;
typedef long long ll;
// typedef __int128 it;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int N = 102;
const int M = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-6;
inline int lowbit(int x){
     return x&(-x);}
template<typename T>void write(T x)
{
    
    if(x<0)
    {
    
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
    
        write(x/10);
    }
    putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
    
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){
    if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){
    x = x*10+ch-48;ch=getchar();}x*=f;
}
int n,m,k,T;
bool f[N][N*N];
int a[N];
int b[N];
int fun(int x)
{
    
	return x * x ;
}
void solve()
{
    
   read(n);
   int ans = 0;
   int res = 1e9;
   int sum = 0;
   for(int i=1;i<=n;++i)
   {
    
   	  read(a[i]); ans += fun(a[i]); sum += a[i];
   }
   for(int i=1;i<=n;++i)
   {
    
   	  read(b[i]); ans += fun(b[i]); sum += b[i];
   }
   ans *= (n-2);
   f[0][0] = true;
   for(int i=1;i<=n;++i)
   {
    
   	  for(int j=0;j<=sum;++j)
   	  {
    
   	  	 if(f[i-1][j])
   	  	 {
    
   	  	 	f[i][j+a[i]] = true;
   	  	 	f[i][j+b[i]] = true;
   	  	 }
   	  }
   }
   for(int j=0;j<=sum;++j)
   {
    
   	  if(f[n][j])
   	  {
    
   	  	res = min(res,fun(j)+fun(sum-j));
   	  }
   }
   ans += res;
   write(ans); puts("");
}
signed main(void)
{
      
   // T = 1;
   // OldTomato; cin>>T;
   read(T);
   while(T--)
   {
    
   	 solve();
   }
   return 0;
}