Problem Statement
On a number line, there are $N$ fish swimming.
Fish $i$, which has a weight of $W_i$, is at the coordinate $X_i$ at time $0$ and moves at a speed of $V_i$ in the positive direction.
Takahashi will choose an arbitrary real number $t$ greater than or equal to $0$ and do the following action at time $t$ just once.
Action: Choose an arbitrary real number $x$. Catch all fish whose coordinates are between $x$ and $x+A$, inclusive.
Find the maximum total weight of fish that he can catch.
Constraints
- $1 \leq N \leq 2000$
- $1 \leq A \leq 10^4$
- $1 \leq W_i\leq 10^4$
- $0 \leq X_i\leq 10^4$
- $1 \leq V_i\leq 10^4$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$ $W_1$ $X_1$ $V_1$ $W_2$ $X_2$ $V_2$ $\vdots$ $W_N$ $X_N$ $V_N$
Output
Print the answer.
Sample Input 1
3 10 100 0 100 1 10 30 10 20 10
Sample Output 1
111
At time $0.25$, fish $1$, $2$, and $3$ are at the coordinates $25$, $17.5$, and $22.5$, respectively. Thus, the action done at this time with $x=16$ catches all the fish.
Sample Input 2
3 10 100 100 100 1 10 30 10 20 10
Sample Output 2
100
One optimal choice is to do the action at time $0$ with $x=100$.
Sample Input 3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
枚举我们选择的第一条鱼。那么如果现在的时间是 \(t\)，如果 \(t\) 秒时一条鱼在这条鱼的左边 \(a\) 格以内，那么这条鱼就能被选中。
称这条鱼的右边 \(a\) 格为答案区间，我们可以算出剩下每条鱼进入答案区间的时间和出来的时间，从而算出每条鱼被算入答案的时间区间。其实就是根据速度大小和差了多远去判断。当然，如果一直不在，就不理这条鱼。如果一直都在，就把这个区间设为 \([1,10000]\)。然后现在要选定一个时间，让他被覆盖的次数最多。那么把所有时间离散化，差分就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=13,M=6;
double dp[1<<N][1<<M][N+M],ans;
int n,m,x[N+M],y[N+M],pw[6];
long long sqr(int a)
{
return 1LL*a*a;
}
double dist(int a,int b)
{
return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
}
int popcnt(int x)
{
int cnt=0;
while(x)
cnt+=x&1,x>>=1;
return cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<m;i++)
scanf("%d%d",&x[i+n],&y[i+n]);
for(int i=pw[0]=1;i<=5;i++)
pw[i]=pw[i-1]*2;
for(int i=0;i<(1<<N);i++)
for(int j=0;j<(1<<M);j++)
for(int k=0;k<(N+M);k++)
dp[i][j][k]=1e16;
for(int i=0;i<n;i++)
dp[1<<i][0][i]=dist(n+m,i);
for(int i=0;i<m;i++)
dp[0][1<<i][i+n]=dist(n+m,i+n);
ans=1e16;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<(1<<m);j++)
{
int k=popcnt(j);
for(int x=0;x<n;x++)
{
if(!(i>>x&1))
continue;
for(int y=0;y<n;y++)
{
if(x==y||!(i>>y&1))
continue;
dp[i][j][x]=min(dp[i][j][x],dp[i^1<<x][j][y]+dist(x,y)/pw[k]);
}
for(int y=n;y<m+n;y++)
{
if(!(j>>(y-n)&1))
continue;
dp[i][j][x]=min(dp[i][j][x],dp[i^1<<x][j][y]+dist(x,y)/pw[k]);
}
if(i==(1<<n)-1)
ans=min(ans,dp[i][j][x]+dist(x,n+m)/pw[k]);
// printf("%d %d %d %.6lf\n",i,j,x,dp[i][j][x]) ;
}
--k;
for(int x=0;x<m;x++)
{
if(!(j>>x&1))
continue;
for(int y=0;y<n;y++)
{
if(!(i>>y&1))
continue;
dp[i][j][x+n]=min(dp[i][j][x+n],dp[i][j^1<<x][y]+dist(y,x+n)/pw[k]);
}
for(int y=0;y<m;y++)
{
if(!(j>>y&1))
continue;
dp[i][j][x+n]=min(dp[i][j][x+n],dp[i][j^1<<x][y+n]+dist(y+n,x+n)/pw[k]);
}
if(i==(1<<n)-1)
ans=min(ans,dp[i][j][x+n]+dist(x+n,n+m)/pw[k+1]);
// printf("%d %d %d %.6lf\n",i,j,x+n,dp[i][j][x+n]) ;
}
}
}
printf("%.10lf",ans);
}
原文地址：http://www.cnblogs.com/mekoszc/p/16907302.html
