行车(a1*b1+a1*b2+..a1*bn+a2*b1+...an*bn=(a1+..an)(b1+..bn) )
行车
(bicycle.pas/cpp)
题目描述
骑在自行车上，让微风追逐着他衣角，在不经意间捕获着一颗颗芳心，骄阳似乎也没有此时的他耀眼，这便是机房的骄傲——建德！
这是每天都会发生在附中门口的一幕。而为了每天能够领略不同的风景，捕获更多的芳心，建德打算制定n 条线路。为了简化起见，我们把这个世界想象成一个平面直角坐标系，而建德所在的福建师大附中则为原点。由于建德不能绕的太进，他每次路线的目的地都被限制在一个对应的右上角为(x, y)，左下角为(-x,-y)的矩形内。
每次建德都会从原点直接沿直线走到目的地。显然，他走过了一个向量，这被数学控的“毛毡”称为这次的路线向量。他为了更好地规划线路，为每条线路定义了一个无聊值，即这次的路线向量和其余所有乊前的线路的向量的点积和【对于向量(x1,y1),(x2,y2),他们的点积和即为x1*x2+y1*y2】。建德希望合理的选择目的地，使得所有线路的无聊值乊和最小。
输入格式
第一行一个正整数n ，表示建德打算制定n 条旅行线路。
接下来 n 行，每行两个整数x , y ，描述一个限制目的地的矩形。
输出格式
一行一个整数，即最小的无聊值，保留 2 位小数。
样例输入
2
1 2
2 1
样例输出
-4.00
数据范围与约定
对于10% 的数据，保证0<n<=5，0<x,y<=5。
对于 30% 的数据，保证0<n<=20，0<x,y<=100。
对于 100% 的数据，保证0<n<=200，0<x,y<=200。
首先 根据公式 n个数和m个数两两相乘的结果为n个数的和与m个数的和的积
而且x和y互不影响
于是套公式-两两相乘/2-交集 结果为 f(n)= （x1+..+xn)^2+x1^2+..xn^2 )/2
易证 f(n)=(x1+...+xn-1)* xn + f(n-1)
所以 xn 要么最大，要么最小 才能使 f(n)有最大/最小值
因为不知道 (x1+..x(n-1)的正负 所以只能靠猜（ 既考虑最大，也考虑最小）
回到原公式 显然 要是 f(n)有最小值 就要另 （x1+..+xn)有最小值
于是就是分组背包各种做……
[cpp]
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define MAXV ((40000+100)*2)
#define MAXX (200+10)
#define f(i,j) f[ (i) ][ (j)+20000 ]
int n;
long long ans=0;
bool f[MAXN][MAXV];
int x[MAXN];
int y[MAXN];
int sqr(int x)
{
return x*x;
}
int main()
{
freopen("bicycle.in","r",stdin);
freopen("bicycle.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
ans-=(long long)(sqr(x[i]))+sqr(y[i]);
}
memset(f,0,sizeof(f));
f(0,0)=1;
for (int i=1;i<=n;i++)
for (int j=-i*200;j<=i*200;j++)
f(i,j)=f(i-1,j-x[i])||f(i-1,j+x[i]);
int j=0;
while (!f(n,j)&&!f(n,-j)) j++;
ans+=(long long)j*j;
// cout<<j<<endl;
/* int j=0;
for (int i=0;i<=n;i++)
{
for (int j=-10;j<=10;j++)
cout<<f(i,j);
cout<<endl;
}
*/
memset(f,0,sizeof(f));
f(0,0)=1;
for (int i=1;i<=n;i++)
for (int j=-i*200;j<=i*200;j++)
f(i,j)=f(i-1,j-y[i])||f(i-1,j+y[i]);
j=0;
while (!f(n,j)&&!f(n,-j)) j++;
ans+=(long long)j*j;
cout.setf(ios::fixed);
cout.precision(2);
cout<<double(ans)/2<<endl;
// while (1);
return 0;
}
补充：软件开发 , C++ ,
