社区讨论
90Pts求调(WA on #11)
P2466[SDOI2008] Sue 的小球参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mlmapbow
- 此快照首次捕获于
- 2026/02/14 20:31 5 天前
- 此快照最后确认于
- 2026/02/18 14:40 22 小时前
rt,问了Deepseek,他帮我写了注释但貌似没有解决问题
CPP#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1005;
const int M = 20010;
const int dx = 10000; // 偏移量,用于将坐标映射到非负下标
struct pnt
{
int x, y, v; // 横坐标、纵坐标总和、速度总和
} pl[N], pr[N]; // 左侧点(包括起点)和右侧点(包括起点)
int cnt1 = 0, cnt2 = 0;
long long suml[N], sumr[N]; // 左侧和右侧速度前缀和
long long sv = 0, sy = 0; // 所有彩蛋的速度总和、初始纵坐标总和
int n, xs;
int y[M], v[M]; // 按坐标偏移后累加的纵坐标和速度
__int128 f[N][N][2]; // DP 数组,0 表示停在左端,1 表示停在右端
// 计算从 s 移动到 t 的代价
long long w(int li, int ri, int s, int t)
{
return (sv - suml[li] - sumr[ri]) * abs(s - t);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> xs;
int xi[N], yi[N], vi[N];
for(int i = 1; i <= n; i++) cin >> xi[i];
for(int i = 1; i <= n; i++) cin >> yi[i];
for(int i = 1; i <= n; i++) cin >> vi[i];
// 将相同横坐标的彩蛋合并(题目保证每个坐标可能有多个彩蛋)
for(int i = 1; i <= n; i++)
{
y[xi[i] + dx] += yi[i];
v[xi[i] + dx] += vi[i];
}
// 处理起点处的彩蛋(如果有)
sy = y[xs + dx]; // 起点处的纵坐标直接加入总分(0时刻收集)
y[xs + dx] = 0; // 清零,避免重复加入列表
v[xs + dx] = 0; // 速度清零,不计入下落损失
// 构建左侧列表(包含起点作为虚拟点)
cnt1++;
pl[cnt1] = {xs, 0, 0};
for(int i = xs + dx - 1; i >= 0; i--) // 从起点左边开始向左扫描
{
if(y[i] != 0)
{
cnt1++;
pl[cnt1] = {i - dx, y[i], v[i]};
}
}
// 构建右侧列表(包含起点作为虚拟点)
cnt2++;
pr[cnt2] = {xs, 0, 0};
for(int i = xs + dx + 1; i < M; i++) // 从起点右边开始向右扫描
{
if(y[i] != 0)
{
cnt2++;
pr[cnt2] = {i - dx, y[i], v[i]};
}
}
// 计算前缀和、总纵坐标、总速度
for(int i = 1; i <= cnt1; i++)
{
suml[i] = suml[i - 1] + pl[i].v;
sy += pl[i].y; // 累加左侧彩蛋的纵坐标
}
for(int i = 1; i <= cnt2; i++)
{
sumr[i] = sumr[i - 1] + pr[i].v;
sy += pr[i].y; // 累加右侧彩蛋的纵坐标
}
sv = suml[cnt1] + sumr[cnt2]; // 所有非起点彩蛋的速度总和
// 初始化 DP
memset(f, 0x7f, sizeof(f));
f[1][1][0] = f[1][1][1] = 0; // 初始时位于起点,代价为0
// DP 转移
for(int i = 1; i <= cnt1; i++)
{
for(int j = 1; j <= cnt2; j++)
{
if(i != 1)
f[i][j][0] = min(f[i][j][0], f[i-1][j][0] + w(i-1, j, pl[i-1].x, pl[i].x));
if(j != 1)
f[i][j][1] = min(f[i][j][1], f[i][j-1][1] + w(i, j-1, pr[j-1].x, pr[j].x));
// 从另一端点转移(注意 i=1 且 j=1 时两端相同,代价为0)
if(i != 1 || j != 1)
{
f[i][j][0] = min(f[i][j][0], f[i][j][1] + w(i, j, pl[i].x, pr[j].x));
f[i][j][1] = min(f[i][j][1], f[i][j][0] + w(i, j, pr[j].x, pl[i].x));
}
}
}
long long mw = min(f[cnt1][cnt2][0], f[cnt1][cnt2][1]); // 最小总损失
double res = (sy - mw) / 1000.0; // 最终得分
printf("%.3f\n", res);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...