Description
Input
Output
Sample Input
4
4 5
1 2
3 3
4 1
4 5
1 2
3 3
4 1
Sample Output
-38.00
HINT
题解
一道很巧妙的dp。
要我们最小化sigma(xi*xj+yi*yj)。原式可化为:[(x1+x2+...+xn)^2-(x1^2+x2^2+...xn^2)+(y1+y2+...+yn)^2-(y1^2+y2^2+...+yn^2)]/2应为要最小化,x1^2+x2^2+...xn^2一定是取题目所给的那个“边界值”时最大,y1^2+y2^2+...+yn^2同理。此时就要求我们要得到绝对值最小的x1+x2+...+xn与y1+y2+...+yn。一个简单的dp就可以了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long #define MAXN 40000 using namespace std; int n; int x[202],y[202],a[202],f[202][80002]; ll ans; void init() { scanf("%d",&n); int i; for(i=1;i<=n;i++) {scanf("%d%d",&x[i],&y[i]); ans-=x[i]*x[i]+y[i]*y[i]; } } void dp() { int i,j; for(i=1;i<=n;i++) a[i]=x[i]; f[0][MAXN]=1; for(i=1;i<=n;i++) for(j=-MAXN;j<=MAXN;j++) {if(f[i-1][j+MAXN]) {f[i][j+MAXN+a[i]]=f[i][j+MAXN-a[i]]=1;} } for(i=0;i<=MAXN;i++) {if(f[n][MAXN+i]||f[n][MAXN-i]) {ans+=i*i; break;} } memset(f,0,sizeof(f)); for(i=1;i<=n;i++) a[i]=y[i]; f[0][MAXN]=1; for(i=1;i<=n;i++) for(j=-MAXN;j<=MAXN;j++) {if(f[i-1][j+MAXN]) {f[i][j+MAXN+a[i]]=f[i][j+MAXN-a[i]]=1;} } for(i=0;i<=MAXN;i++) {if(f[n][MAXN+i]||f[n][MAXN-i]) {ans+=i*i; break;} } printf("%.2lf\n",double(ans/2)); } int main() { init(); dp(); return 0; }