cf1637_D. Yet Another Minimization Problem

链接:https://codeforces.com/contest/1637/problem/D 题意:给你两个数组 a , b a,b a,b,可以无限次进行以下操作:交换 a i , b i ai,bi ai,bi的值. 要求你进行上述操作后,求得下列表达式的最小值. ∑ i = 1 n ∑ j = i + 1 n ( a i + a j ) 2 + ∑ i = 1 n ∑ j = i + 1 n ( b i + b j ) 2 \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} i=1∑n​j=i+1∑n​(ai​+aj​)2+i=1∑n​j=i+1∑n​(bi​+bj​)2 思路:对于这类题目尝试通过化简后得到某些定值与变量,通过枚举变形后的变量从而求解. 先只关心 a i a_i ai​数组, ∑ i = 1 n ∑ j = i + 1 n ( a i + a j ) 2 = ∑ i = 1 n ∑ j = i + 1 n ( a i 2 + a j 2 + 2 a i a j ) \sum_{i=1}^n\sum_{j=i+1}^n{(a_i+a_j)^2}= \sum_{i=1}^n\sum_{j=i+1}^n{(a_i^2+a_j^2+2a_ia_j)} ∑i=1n​∑j=i+1n​(ai​+aj​)2=∑i=1n​∑j=i+1n​(ai2​+aj2​+2ai​aj​) 在这一步上稍作停顿,不难发现 a i 2 与 a j 2 在 求 和 后 应 该 是 一 个 定 值 , 我 们 尝 试 把 它 从 求 和 符 号 中 提 取 出 来 a_i^2与a_j^2在求和后应该是一个定值,我们尝试把它从求和符号中提取出来 ai2​与aj2​在求和后应该是一个定值,我们尝试把它从求和符号中提取出来.继续化简 上 式 = n − 1 ∗ ∑ i = 1 n a i 2 + ∑ i = 1 n ∑ j = i + 1 n ( 2 a i a j ) 上式=n-1*\sum_{i=1}^n{a_i^2}+\sum_{i=1}^n\sum_{j=i+1}^n{(2a_ia_j)} 上式=n−1∗∑i=1n​ai2​+∑i=1n​∑j=i+1n​(2ai​aj​) 不难发现,求和的前半部分是一个定值.再考虑加入 b i b_i bi​数组,式子变为. ( n − 1 ) ∗ ∑ i = 1 n a i 2 + ( n − 1 ) ∗ ∑ i = 1 n b i 2 + ∑ i = 1 n ∑ j = i + 1 n ( 2 a i a j ) + ∑ i = 1 n ∑ j = i + 1 n ( 2 b i b j ) (n-1)*\sum_{i=1}^n{a_i^2}+(n-1)*\sum_{i=1}^n{b_i^2}+\sum_{i=1}^n\sum_{j=i+1}^n{(2a_ia_j)}+\sum_{i=1}^n\sum_{j=i+1}^n{(2b_ib_j)} (n−1)∗i=1∑n​ai2​+(n−1)∗i=1∑n​bi2​+i=1∑n​j=i+1∑n​(2ai​aj​)+i=1∑n​j=i+1∑n​(2bi​bj​) 对于乘积部分似乎仍然能继续化简, 令 s u m = ∑ i = 1 n a i 。 ∑ i = 1 n ∑ j = i + 1 n ( 2 a i a j ) 到 这 一 步 的 转 化 就 很 艰 难 了 , 需 要 我 们 集 中 注 意 力 到 令sum=\sum_{i=1}^nai 。\sum_{i=1}^n\sum_{j=i+1}^n{(2a_ia_j)} 到这一步的转化就很艰难了,需要我们集中注意力到 令sum=∑i=1n​ai。∑i=1n​∑j=i+1n​(2ai​aj​)到这一步的转化就很艰难了,需要我们集中注意力到i上$,通过在纸上打打表找规律. 不难发现多出来的 2 a i a j 可 以 配 给 其 他 括 号 , 化 简 得 到 式 子 ∑ i = 1 n ∑ j = i + 1 n ( 2 a i a j ) = ∑ i = 1 n ( a i ∗ ( s u m − a i ) ) = ∑ i = 1 n a i ∗ s u m − a i 2 = s u m 2 − ∑ i = 1 n a i 2 2aiaj可以配给其他括号,化简得到式子\sum_{i=1}^n\sum_{j=i+1}^n{(2a_ia_j)}=\sum_{i=1}^n(ai*(sum-ai))=\sum_{i=1}^n{ai*sum-ai^2}=sum^2-\sum_{i=1}^na_i^2 2aiaj可以配给其他括号,化简得到式子∑i=1n​∑j=i+1n​(2ai​aj​)=∑i=1n​(ai∗(sum−ai))=∑i=1n​ai∗sum−ai2=sum2−∑i=1n​ai2​ 代入回总的式子整理得: ( n − 2 ) ∗ ∑ i = 1 n ( a i 2 + b i 2 ) + ( ∑ i = 1 n a i ) 2 + ( ∑ i = 1 n b i ) 2 (n-2)*\sum_{i=1}^n{(a_i^2+b_i^2)}+(\sum_{i=1}^n{a_i})^2+(\sum_{i=1}^n{b_i})^2 (n−2)∗i=1∑n​(ai2​+bi2​)+(i=1∑n​ai​)2+(i=1∑n​bi​)2 式子第一部分是一个定值,只需让右边最大即可.问题转化为求得最小化两个数组求和的平方之和. 我们想要枚举出这个数组和的可能性,然后找到一个最优的解,那么问题又转化为如何求得这个数组所有可能的取值. 每个位置i,要么是选 a i , 要 么 是 选 b i a_i,要么是选b_i ai​,要么是选bi​这是经典的01背包问题.令 d p i , w dp_{i,w} dpi,w​为考虑第i个物品时,w是否能成为一个可能sum值.转移 d p ( i , w ) ∣ = ( d p ( i − 1 , w − a i ) ∣ ∣ d p ( i − 1 , w − b i ) ) dp(i,w)|=(dp(i-1,w-ai)||dp(i-1,w-bi)) dp(i,w)∣=(dp(i−1,w−ai)∣∣dp(i−1,w−bi))

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 100*100+5;
const int INF = 1e9+7;
typedef pair pii;
int a[105],b[105];
bool dp[101][maxn];
int main(){
//	freopen("1.txt","r",stdin);
	int T;cin>>T;
	while(T--){
		int n;scanf("%d",&n);
		ll pow_sum=0;ll sum = 0;
		memset(dp,0,sizeof(dp));
		for(int i=1;i