WA两个点求调
查看原帖
WA两个点求调
1055410
ThySecret楼主2024/11/22 12:20
#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m, L;
int x[N], t[N], minn[N][N][2], dp[N][N][2];
    // minn[i][j][2] 表示扩展至 dp(i, j)[0 / 1] 的最大点数的最小时间
int ans;

inline int dist(int x, int y)
{
    if (x <= n + 1 && n + 1 <= y) return ::x[x] + ::x[y];
    else return abs(::x[y] - ::x[x]);
}

signed main()
{
    File("b");
    read(n, L);
    for (int i = 1; i <= n; i ++) read(x[i]);
    for (int i = 1; i <= n; i ++) read(t[i]);
    reverse(x + 1, x + 1 + n), reverse(t + 1, t + 1 + n);
    for (int i = 1; i <= n; i ++)
        x[i + n + 1] = L - x[i], t[i + n + 1] = t[i];
    x[n + 1] = t[n + 1] = 0, m = 2 * n + 1;

    memset(minn, 0x3f, sizeof minn), memset(dp, 0, sizeof dp);
    minn[n + 1][n + 1][0] = minn[n + 1][n + 1][1] = 0;

    // for (int i = 1; i <= m; i ++) DEBUG(i, x[i], t[i]);

    for (int len = 2; len <= n + 1; len ++)
    {
        for (int l = n + 1 - len + 1; l <= n + 1; l ++)
        {
            int r = l + len - 1;
            
            for (int k = l + 1; k <= r; k ++)
            {
                if (t[l] - minn[k][r][0] >= dist(l, k))
                {
                    if (dp[l][r][0] <= dp[k][r][0]) 
                        dp[l][r][0] = dp[k][r][0] + 1, minn[l][r][0] = minn[k][r][0] + dist(l, k);
                    else if (dp[l][r][0] == dp[k][r][0] + 1 && minn[l][r][0] > minn[k][r][0] + dist(l, k))
                        minn[l][r][0] = minn[k][r][0] + dist(l, k);
                }
                if (t[l] - minn[k][r][1] >= dist(l, r))
                {
                    if (dp[l][r][0] <= dp[k][r][1])
                        dp[l][r][0] = dp[k][r][1] + 1, minn[l][r][0] = minn[k][r][1] + dist(l, r);
                    else if (dp[l][r][0] == dp[k][r][1] + 1 && minn[l][r][0] > minn[k][r][1] + dist(l, r))
                        minn[l][r][0] = minn[k][r][1] + dist(l, r);
                }
            }
            for (int k = l; k <= r - 1; k ++)
            {
                if (t[r] - minn[l][k][1] >= dist(k, r))
                {
                    if (dp[l][r][1] <= dp[l][k][1])
                        dp[l][r][1] = dp[l][k][1] + 1, minn[l][r][1] = minn[l][k][1] + dist(k, r);
                    else if (dp[l][r][1] == dp[l][k][1] + 1 && minn[l][r][1] > minn[l][k][1] + dist(k, r))
                        minn[l][r][1] = minn[l][k][1] + dist(k, r);
                }
                if (t[r] - minn[l][k][0] >= dist(l, r))
                {
                    if (dp[l][r][1] <= dp[l][k][0])
                        dp[l][r][1] = dp[l][k][0] + 1, minn[l][r][1] = minn[l][k][0] + dist(l, r);
                    else if (dp[l][r][1] == dp[l][k][0] + 1 && minn[l][r][1] > minn[l][k][0] + dist(l, r))
                        minn[l][r][1] = minn[l][k][0] + dist(l, r);
                }
            }

            ans = max(ans, max(dp[l][r][0], dp[l][r][1]));
        }
    }
    cout << ans << '\n';

    return 0;
}

阿里嘎多

2024/11/22 12:20
加载中...