首页 > 代码库 > noip 模拟赛 After 17（递推+特殊的技巧）
noip 模拟赛 After 17（递推+特殊的技巧）
来源：Violet_II T1
好神的一题，我竟然没做出来QAQ
首先我们发现，答案是sigma(x[i]*x[j], i>j)+sigma(y[i]*y[j], i>j)。显然只需要讨论左边的就行了，右边就可以同理了。
我们发现sigma(x[i]*x[j], i>j)=(sigma(x[i])^2-sigma(x[i]^2))/2，减号后边和除以2显然是常数也就是说确定了x[i]也就确定了值。但是x[i]的值有哪些可以取呢？我们发现在sigma(x[i]*x[j], i>j)中，因为x[j]的取值与x[i]无关，所以对于x[i]，假定所有i>j都确定了，那么也就是x[i]*sigma(x[j])，所以这是一个一次函数，我们对他取极值就行了。那么x[i]的值我们确定了，就是给定数据的x[i]或-x[i]。
那么问题转化为求最小的|sigma(x[i])|，注意这是绝对值。
我们考虑像背包那样，d[i][j]表示前i个物体，体积为j是否能被取到，那么
d[i][j+a[i]]=1 当 d[i-1][j]=1
d[i][j-a[i]]=1 当 d[i-1][j]=1
初始化 d[0][0]=1
那么就行了。。。。
好神。。
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cstdlib>#include <cstring>#include <map>typedef long long ll;#define read(x) x=getint()#define dbg(x) cout << (#x) << " = " << x << endl#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i, a, n) for(int i=(a); i<=(n); ++i)#define for2(i, a, n) for(int i=(a); i<(n); ++i)#define for3(i, a, n) for(int i=(a); i>=(n); --i)#define for4(i, a, n) for(int i=(a); i>(n); --i)#define CC(a, n) memset(a, n, sizeof(a))using namespace std;inline const ll getint() { ll r=0, k=1; char ch=getchar(); for(; ch<‘0‘||ch>‘9‘; ch=getchar()) if(ch==‘-‘) k=-1; for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) r=r*10+ch-‘0‘; return r*k; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=400;int x[N], y[N], n, ans;bool d[2][N*N*2];int dp(int *a) { int sum=0, S=N*N, pos=0; CC(d, 0); d[pos^1][S]=1; for1(i, 1, n) { for1(j, S-sum-a[i], S+sum+a[i]) d[pos][j]=0; for1(j, S-sum-a[i], S+sum+a[i]) if(d[pos^1][j]) d[pos][j+a[i]]=1, d[pos][j-a[i]]=1; sum+=a[i]; pos^=1; } pos^=1; int mn=~0u>>1; for1(i, S, S+sum) if(d[pos][i]) { mn=min(mn, i-S); break; } for3(i, S, S-sum) if(d[pos][i]) { mn=min(mn, S-i); break; } return mn*mn;}int main() { read(n); for1(i, 1, n) read(x[i]), read(y[i]); for1(i, 1, n) ans-=x[i]*x[i]; for1(i, 1, n) ans-=y[i]*y[i]; ans+=dp(x); ans+=dp(y); printf("%.2lf\n", (double)ans/(double)2); return 0;}
题目描述
今天是 Cheer 的 17 岁生日,而她 17 岁这年最大的梦想就是出去远行。为此,她打算制
定 n 条旅行线路。
为了简化起见,我们把这个世界想象成一个平面直角坐标系,而 Cheer 所在的小镇则为
原点。由于父亲不让 Cheer 走得太远,她每次旅行的目的地都被限制在一个对应的右上角为
( x , y ) ,左下角为 ( ? x , ? y ) 的矩形内。
每次 Cheer 都会从原点直接沿直线走到目的地。显然,她走过了一个向量,这被数学控
的 Cheer 称为这次的旅行向量。Cheer 为了更好地规划旅行线路,为每条旅行线路定义了一
个无聊值,即这次的旅行向量和其余所有之前的线路的旅行向量的点积和。
Cheer 希望合理的选择目的地,使得所有旅行线路的无聊值之和最小。
输入格式
第一行一个正整数 n ,表示 Cheer 打算制定 n 条旅行线路。
接下来 n 行,每行两个整数 x , y ,描述一个限制目的地的矩形。
输出格式
一行一个整数,即最小的无聊值,保留 2 位小数。
样例输入
2
1 2
2 1
样例输出
-4.00
数据范围与约定
对于 10% 的数据,保证 ? ? n ? ? , ? ? x, y ? ? 。
对于 30% 的数据,保证 ? ? n ? ?? , ? ? x, y ? ??? 。
对于 100% 的数据,保证 ? ? n ? ??? , ? ? x, y ? ??? 。
noip 模拟赛 After 17（递推+特殊的技巧）