NC20312. [SDOI2008]SUE的小球
描述
输入描述
第一行为两个整数N, x0用一个空格分隔，表示彩蛋个数与Sue的初始位置。第二行为N个整数xi，每两个数用一个空格分隔，第i个数表示第i个彩蛋的初始横坐标。第三行为N个整数yi，每两个数用一个空格分隔，第i个数表示第i个彩蛋的初始纵坐标。第四行为N个整数vi，每两个数用一个空格分隔，第i个数表示第i个彩蛋匀速沿y轴负方向下落的的速度。
输出描述
一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。
示例1
输入:
3 0 -4 -2 2 22 30 26 1 9 8
输出:
0.000
C++14(g++5.4) 解法, 执行用时: 41ms, 内存消耗: 8336K, 提交时间: 2019-08-05 10:21:21
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1005;
int dp[2][maxn][maxn];
int w[maxn];
struct node
{
int x,y,v;
}p[maxn];
bool cmp(node xx, node yy)
{
return xx.x==yy.x ? xx.y<yy.y : xx.x<yy.x;
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int n,x0;
cin>>n>>x0;
for(int i=1;i<=n;i++) cin>>p[i].x;
for(int i=1;i<=n;i++) cin>>p[i].y;
for(int i=1;i<=n;i++) cin>>p[i].v;
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++) w[i]=w[i-1]+p[i].v;
for(int i=1;i<=n;i++) dp[0][i][i]=dp[1][i][i]=p[i].y-abs(p[i].x-x0)*w[n];
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
dp[0][i][j]=p[i].y+max(dp[0][i+1][j]-abs(p[i+1].x-p[i].x)*(w[n]-w[j]+w[i]),dp[1][i+1][j]-abs(p[j].x-p[i].x)*(w[n]-w[j]+w[i]));
dp[1][i][j]=p[j].y+max(dp[1][i][j-1]-abs(p[j-1].x-p[j].x)*(w[n]-w[j-1]+w[i-1]),dp[0][i][j-1]-abs(p[j].x-p[i].x)*(w[n]-w[j-1]+w[i-1]));
}
printf("%.3lf\n",(double)(max(dp[0][1][n],dp[1][1][n])/1000.));
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 14ms, 内存消耗: 7332K, 提交时间: 2022-08-18 23:16:34
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,v;
bool operator<(const node &p)
{
return x<p.x;
}
}a[1005];
int n,x0,pre[1005],dp[1005][1005][2];
int main()
{
cin>>n>>x0;
for(int i=1;i<=n;i++) cin>>a[i].x;
for(int i=1;i<=n;i++) cin>>a[i].y;
for(int i=1;i<=n;i++) cin>>a[i].v;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i].v;
for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=a[i].y-abs(a[i].x-x0)*pre[n];
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
int t1=pre[n]-pre[r]+pre[l],t2=pre[n]-pre[r-1]+pre[l-1];
dp[l][r][0]=a[l].y+max(dp[l+1][r][0]-abs(a[l+1].x-a[l].x)*t1,dp[l+1][r][1]-abs(a[r].x-a[l].x)*t1);
dp[l][r][1]=a[r].y+max(dp[l][r-1][0]-abs(a[l].x-a[r].x)*t2,dp[l][r-1][1]-abs(a[r].x-a[r-1].x)*t2);
}
}printf("%.3f",max(dp[1][n][0],dp[1][n][1])*0.001);
}