Gym - 100215G Andrew Stankevich Contest 12 (ASC 12)
题意
给定两条管道的起点和终点（注意这两条都是直线不是线段），再给 \(n\) 个点，坐标为 \((x_i,y_i)\)，石油需求量为 \(d_i\)，你要从这 \(n\) 个点向它们最近的那条管道连接，花费为需求量乘以连接长度。你还要保证向两条管道连接的人的数量足够均衡，即保证两边人数的差小于等于 \(c\)，求使总花费最小的方案。
思路
先求出两条直线的斜率，\(k=\dfrac{y_2-y_1}{x_2-x_1}\)，\(b=y_2-k\cdot x_2\)，注意分母或分子为 \(0\) 时要特判。
首先求出每个点到两个管道的距离，即点到直线距离公式，\(d=\dfrac{|kx-y+b|}{\sqrt{k^2+1}}\)。设每个点与第一条和第二条的距离分别为 \(dis_{i,0}\) 和 \(dis_{i,1}\)。
然后去做动态规划，设 \(f_{i,j}\) 表示前 \(i\) 个管道，有 \(j\) 个连向第一个管道的最小花费。
转移显而易见：\(f_{i,j}=\min(f_{i-1,j-1}+dis_{i,0},f_{i-1,j}+dis_{i,1})\)。注意下标不要越界。
转移过程中记得用变量记录每个 \(i,j\) 是从哪个 \(j\) 转移过来的。最后直接还原输出即可。
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long double ld;
const int inf=2e9;
const int N=205;
inline void FileIO(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);
}
ld f[N][N];
ld X[2][2],Y[2][2];
ld x[N],y[N],d[N];
ld dis[N][2];
ld k[2],b[2];
int prv[N][N];
ld myabs(ld x){if(x>0) return x;return -x;
}
ld calc(int i,int j){if(Y[j][0]==Y[j][1]) return myabs(Y[j][0]-y[i]);else if(X[j][0]==X[j][1]) return myabs(X[j][0]-x[i]);ld d3=myabs(k[j]*x[i]-y[i]+b[j])/sqrt(k[j]*k[j]+1);return d3;
}
void solve(){int n,C; cin>>n>>C;for(int i=0;i<2;i++) for(int j=0;j<2;j++) cin>>X[i][j]>>Y[i][j];//求直线解析式k[0]=(Y[0][0]-Y[0][1])/(X[0][0]-X[0][1]); b[0]=Y[0][1]-k[0]*X[0][1];k[1]=(Y[1][0]-Y[1][1])/(X[1][0]-X[1][1]); b[1]=Y[1][1]-k[1]*X[1][1];//读入和计算距离for(int i=1;i<=n;i++){cin>>x[i]>>y[i]>>d[i];dis[i][0]=d[i]*calc(i,0);dis[i][1]=d[i]*calc(i,1);}//dp转移过程for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=inf;f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=i;j++){if(j==0){f[i][j]=min((ld)inf,f[i-1][j]+dis[i][1]);prv[i][j]=j;}else{ld c1=f[i-1][j-1]+dis[i][0],c2=f[i-1][j]+dis[i][1];if(c1<c2) prv[i][j]=j-1;else prv[i][j]=j;f[i][j]=min(c1,c2);}}}//找到最小花费及位置ld mn=inf;int pos=-1;for(int j=0;j<=n;j++){int k=n-j;if(abs(j-k)>C) continue;if(f[n][j]<mn){mn=f[n][j];pos=j;}}//还原路径vector<int> ans;for(int i=n;i>=1;i--){ans.push_back(2-(pos-prv[i][pos]));pos=prv[i][pos];}reverse(ans.begin(),ans.end());for(int x:ans) cout<<x<<" ";cout<<endl;
}
main(){FileIO("pipe");solve();
}