社区讨论

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 条回复,欢迎继续交流。

正在加载回复...