ABC219H 题解

· · 个人记录

ABC219H 题解

ABC219H Candles

题意

坐标轴上放着 N 个蜡烛。第 i 个蜡烛位于 X_i，初始长度为 A_i。所有蜡烛一开始都是点燃的。一开始高桥站在坐标 0 的位置（即原点）。

每过 1 秒，所有点燃的蜡烛的长度都会减少 1，减到 0 为止。高桥每次可以选择向左或者向右移动 1 个单位长度，消耗时间 1 秒。

当高桥到达一个蜡烛的时候，他可以把蜡烛吹灭；此时蜡烛不会继续燃烧，不会减少长度了。

问：最后蜡烛能剩下的最长长度是多少？

1\le N\le300 -10^9\le X_i\le 10^9 1\le A_i\le 10^9

题目分析

Part 1

P1220 关路灯

注意到本题的限制：蜡烛的长度不会减到负数。这是和 P1220 唯一的区别。

考虑一个简单的版本：蜡烛可以烧到负数。这题就变成了 P1220。

dp 初始值为所有蜡烛长度的和，然后直接做就好了。

转移方程大致就是 $-1\times dist\times the\_number\_of\_the\_remaining\_candle+dp(i,j,0/1)\rightarrow dp(i-1,j,0/1)\ ,\ dp(i,j+1,1/0)$，具体步骤不在赘述。 #### Part 2 考虑本题：蜡烛不可以烧到负数，在 $0$ 的时候熄灭了。 从最终的结果反着倒推过程，容易发现蜡烛分为两种：在到达前烧完的，到了这里吹灭的。 本题难点就在于，**我们无法准确知道哪些蜡烛会自己烧完**。 不妨把这个影响因素设计入 dp 状态：$dp(i,j,k,0/1)$，$i,j,0/1$ 同原来一样，$k$ 表示**还未到达的部分，可能提前自己烧完的蜡烛的数量**。 观察简化版的转移方程，每次转移就是把所有**燃着的**蜡烛减掉一部分。现在，所有燃着的蜡烛，就是 $N-k$。 因此，容易想到，为了方便转移、计算，**假设蜡烛可以烧到负数**。 初始值同简化版一样，都是原来蜡烛的总长。 每次转移的时候，新加入的蜡烛都有两种可能： 1. 还点着，转移和原来类似。 $-1\times dist\times (N-(j-i+1)-k) + dp(i,j,k,0/1)\rightarrow dp(i-1,j,k,0/1),dp(i,j+1,k,1/0)$。 2. 已经烧完了，说明这个蜡烛长度是 $0$，并且扣掉的长度没有统计在前面的转移内。我们要把它的长度扣掉。 $-1\times dist\times (N-(j-i+1)-k)-lenth\_of\_the\_candle+ dp(i,j,k,0/1)\rightarrow dp(i-1,j,k-1,0/1),dp(i,j+1,k-1,1/0)

这里，我们不需要知道这个蜡烛到底有没有真正烧完。那么答案一定是所有蜡烛都正常熄灭的情况。

此时所有合法的状态都被合法地统计到了。而不合法的情况，都没有合法情况来的好：烧到负数的蜡烛，还不如直接自己灭掉；没烧到负数的蜡烛我们当成了负数，长度取了 0，那么肯定不如正常吹灭更优。

总状态数 O(N^3)，转移复杂度 O(1)，总复杂度 O(N^3)。

于是乎，这个题就做完了。

认为难理解的（点名批评我自己），这里可以画个图感受一下整个过程。

note：

  1. 注意要对下标排序。
  2. 对于原点，可以另开一个下标为 0，长度为 0 的蜡烛。（虽然我的代码里没有（））（orz hellojim \se）

code

整个代码就上面那两个方程的实现。式子稍微有点长，耐着性子自己推一推，誊到代码里就好了。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define REP(i,j) for(int i=0;i<j;++i)
#define REPA(i,j) for(int i=1;i<=j;++i)
#define vi vector<int>
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
using namespace std;
const int MAXN=330; 
int N;
pair<ll,ll>A[MAXN];
ll dp[MAXN][MAXN][MAXN][2];
ll S=0;
int main(void){
    scanf("%d",&N);
    REP(i,N)scanf("%lld%lld",&A[i].fi,&A[i].se),S+=A[i].se;
    sort(A,A+N);
    int it=0;
    while(it<N&&A[it].fi<0)++it;
    if(it<N)REP(i,N)dp[it][it][i][0]=dp[it][it][i][1]=max(S-A[it].fi*(N-i),S-A[it].fi*(N-i-1)-A[it].se);
    --it;
    if(it>=0)REP(i,N)dp[it][it][i][0]=dp[it][it][i][1]=max(S+A[it].fi*(N-i),S+A[it].fi*(N-i-1)-A[it].se);
    for(int len=2;len<=N;++len){
        for(int l=0,r=len-1;r<N;++l,++r){
            for(int k=0;k<=N-len;++k){
                dp[l][r][k][0]=max(
                max(dp[l+1][r][k][0]-(A[l+1].fi-A[l].fi)*(N-len-k+1),dp[l+1][r][k+1][0]-(A[l+1].fi-A[l].fi)*(N-len-k)-A[l].se),
                max(dp[l+1][r][k][1]-(A[r].fi-A[l].fi)*(N-len-k+1),dp[l+1][r][k+1][1]-(A[r].fi-A[l].fi)*(N-len-k)-A[l].se)
                );
                dp[l][r][k][1]=max(
                max(dp[l][r-1][k][1]-(A[r].fi-A[r-1].fi)*(N-len-k+1),dp[l][r-1][k+1][1]-(A[r].fi-A[r-1].fi)*(N-len-k)-A[r].se),
                max(dp[l][r-1][k][0]-(A[r].fi-A[l].fi)*(N-len-k+1),dp[l][r-1][k+1][0]-(A[r].fi-A[l].fi)*(N-len-k)-A[r].se)
                );
            }
        }
    }
    ll ans=max(dp[0][N-1][0][0],dp[0][N-1][0][1]);
    printf("%lld",ans);
    return 0;
}