南京网站建设推南京网站建设设计,网站制作哈尔滨,建立app,石家庄小学网站建设文章目录题意#xff1a;思路#xff1a;传送门
题意#xff1a;
给你两个长度为nnn的数组a,ba,ba,b#xff0c;每次交换可以选择一个iii#xff0c;交换ai,bia_i,b_iai,bi#xff0c;最小化∑i1n∑ji1n(aiaj)2∑i1n∑ji1n(bibj)2\sum_{i1}^n \sum_{ji1}^n(a_ia_j)…
文章目录题意思路传送门
题意
给你两个长度为nnn的数组a,ba,ba,b每次交换可以选择一个iii交换ai,bia_i,b_iai,bi最小化∑i1n∑ji1n(aiaj)2∑i1n∑ji1n(bibj)2\sum_{i1}^n \sum_{ji1}^n(a_ia_j)^2\sum_{i1}^n \sum_{ji1}^n(b_ib_j)^2∑i1n∑ji1n(aiaj)2∑i1n∑ji1n(bibj)2。
1≤n≤100,1≤ai,bi≤1001\le n\le 100,1\le a_i,b_i\le 1001≤n≤100,1≤ai,bi≤100
思路
首先化简式子∑i1n∑ji1n(aiaj)2(n−1)∗∑i1nai2∑i1n∑j1naiaj\sum_{i1}^n \sum_{ji1}^n(a_ia_j)^2(n-1)*\sum_{i1}^na_i^2\sum_{i1}^n\sum_{j1}^na_ia_j∑i1n∑ji1n(aiaj)2(n−1)∗∑i1nai2∑i1n∑j1naiaj之后将第二项式子改写为(∑i1nai)2−∑i1nai2(\sum_{i1}^na_i)^2-\sum_{i1}^na_i^2(∑i1nai)2−∑i1nai2让后化简一下就是(n−2)∗∑i1nai2(∑i1nai)2(n-2)*\sum_{i1}^na_i^2(\sum_{i1}^na_i)^2(n−2)∗∑i1nai2(∑i1nai)2对于bbb同理不难发现前面一块是定值现在我们只需要最小化(∑i1nai)2(∑i1nbi)2(\sum_{i1}^na_i)^2(\sum_{i1}^nb_i)^2(∑i1nai)2(∑i1nbi)2即可考虑用类似背包dpdpdp求出来∑i1nai\sum_{i1}^na_i∑i1nai所有可能的值注意这里dpdpdp不能继承前一个位置的状态。让后遍历可能的值取最小即可。
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N110,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n;
int a[N],b[N];
int f[N][N*N*2];void solve() {scanf(%d,n);int sum0;for(int i1;in;i) scanf(%d,a[i]),suma[i];for(int i1;in;i) scanf(%d,b[i]),sumb[i];memset(f,0,sizeof(f));f[0][0]1;for(int i1;in;i) {for(int j0;jsum;j) {if(ja[i]) f[i][j]|f[i-1][j-a[i]];if(jb[i]) f[i][j]|f[i-1][j-b[i]];}}int anssum*sum;for(int i0;isum;i) {if(!f[n][i]) continue;ansmin(ans,i*i(sum-i)*(sum-i));}//coutsum ansendl;for(int i1;in;i) {ans(n-2)*(a[i]*a[i]b[i]*b[i]);}printf(%d\n,ans);
}int main() {int _; scanf(%d,_);while(_--) {solve();}return 0;
}
/*
1
2
9 8
72 83
*/
