行車
(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;
}
