codeforces GR19 D(多想想为什么题干一手值域为什么给100，jls yyds)

题目
题意: 给定数组a、b，可以任意交换第i个位置的a[i]和b[i]，使得下图的式子最小。(n<=100,a[i]、b[i]<=100)

思路: 肯定得先化简式子，不然不知道干啥。化简完以后发现不用管平方项，只需要关注两个数组和的平方和最小。可以通过dp求出其中一个数组能取到的所有取值，即可找到最小值。
方法1: f[i][j]: 仅用前i个数，使得和为j。true表示可以凑出来。因为最大值为100，最多1e6. (可以用滚动数组把第一维优化为0、1)
方法2: 不妨把小的数都换到a中，大的数都放在b中。通过dp求出通过交换，a数组新的和，记录最小值。可以用bitset维护a数组通过交换得到新的和。
时间复杂度: O(nmaxmax = 1e6),可以用bitset优化，emmm感觉是8倍?不过题解说是64倍，不太懂.
代码:
bitset

#include
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 a(n+1),b(n+1);
    long long ans = 0; int l = 0,r = 0; //和
    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 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("%lldn",ans);
}
signed main(void)
{
	scanf("%d",&T);
	while(T--)
	solve();
	return 0;
}

普通dp

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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() 四舍五入 ceil() 向上取整 floor() 向下取整
// lower_bound(a.begin(),a.end(),tmp,greater()) 第一个小于等于的
// #define int long long //QAQ
using namespace std;
typedef complex CP;
typedef pair 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);}
templatevoid write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
template 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;
}

codeforces GR19 D(多想想为什么题干一手值域为什么给100，jls yyds)

C/C++/C#相关栏目本月热门文章