This way
题意:
给你一个长度为n的a数组和b数组,你每次可以选择一个位置i,交换a[i],b[i]。最终要使得∑i=1n∑j=i+1n(a[i]+a[j])2+∑i=1n∑j=i+1n(b[i]+b[j])2\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(a[i]+a[j])^2+\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(b[i]+b[j])^2i=1∑nj=i+1∑n(a[i]+a[j])2+i=1∑nj=i+1∑n(b[i]+b[j])2最小。
问你这个最小的值是多少。
题解:
这是1800?我都想不出来…
这种化公式的题目好像有段时间没遇到了,我都没有往那方面想。
差不多是这么个过程,那么公式的最后中a和b的平方和我们已经知道了,那么要找的就是后两项最小。
假设a的和为x,那么b的和就是所有数加起来-x呗。看看对于所有a的和情况是否有可能
dp[i][j]表示到了第i个数的时候,a的和为j的可能性
那么状态转移有两种情况:
if(j>=a[i])dp[1-i%2][j]|=dp[i%2][j-a[i]];if(j>=b[i])dp[1-i%2][j]|=dp[i%2][j-b[i]];
#include
using namespace std;
const int N=105;
bool dp[2][N*N];
int a[N],b[N];
int main()
{int t;scanf("%d",&t);while(t--){int n,ans&#61;0,r&#61;0,sum&#61;0;scanf("%d",&n);for(int i&#61;1;i<&#61;n;i&#43;&#43;)scanf("%d",&a[i]),ans&#43;&#61;a[i]*a[i]*(n-2),sum&#43;&#61;a[i];for(int i&#61;1;i<&#61;n;i&#43;&#43;)scanf("%d",&b[i]),ans&#43;&#61;b[i]*b[i]*(n-2),sum&#43;&#61;b[i];memset(dp[1],0,sizeof dp[1]);dp[1][0]&#61;1;for(int i&#61;1;i<&#61;n;i&#43;&#43;){r&#43;&#61;max(a[i],b[i]);memset(dp[1-i%2],0,sizeof dp[1-i%2]);for(int j&#61;r;j>&#61;min(a[i],b[i]);j--){if(j>&#61;a[i])dp[1-i%2][j]|&#61;dp[i%2][j-a[i]];if(j>&#61;b[i])dp[1-i%2][j]|&#61;dp[i%2][j-b[i]];}}int mi&#61;1e9;for(int i&#61;0;i<&#61;r;i&#43;&#43;)if(dp[1-n%2][i])mi&#61;min(mi,i*i&#43;(sum-i)*(sum-i));printf("%d\n",ans&#43;mi);}return 0;
}