题解：P14276 [ROI 2014 Day2] 电影学院

xun_GF_xie · 2025-10-21 15:18:38 · 题解

题目传送门

CSP还有差不多十天了，rp++ 。

本题解做法：线性dp 。

首先我们观察到这道题有一个小坑点：一个电影获奖的欢呼值可能没有其不获奖的欢呼值大。

这个点在贪心中也会出错，所以我们应该将 b_i 和 c_i 的定义更改一下：

那么我们就应该在输入时这样处理：

b[i]-=a[i];
c[i]-=a[i];

::::warning[Hack：欢呼值]

输入：

3
5 9 5
1 5 9
90 10 10

正确输出（例）：

108
1 2

错误输出（例）：

24
3 2

::::

关于求 \text {dp} 状态，我们观察到这道题要求的答案和电影的顺序无关，所以我们可以先将上一个状态选择电影颁奖方案的答案存起来。（记为 x 和 y ，表示前 i 部电影求出的答案里，第 x 个电影获得“最佳导演奖”，第 y 个电影获得“最佳编剧奖”。）

我们先将 dp_2 的答案预处理一下：

然后就能推出 \text {dp} 的状态为：

接着在计算的过程中不断更新 x 和 y 的值就可以了。

但是，如果你真的这么写，大概有 12 个点都是 WA ，那么因为捆绑数据，你会喜提 \color{red} WA \color{red} 0 的。

这时候我们发现第 i 个电影获得两个奖的欢呼值可能都是一样的，这就会使答案错误，那么我们就在 max 里再加上两条 b_i +c_x 和 b_y + c_i 即可。（如果你是贪心，可以算最大值和次大值来比较。）

这是对于 max 中可能出现的五种情况的具体解释：

然后就可以求出正确的 \text {dp} 状态：

::::warning[Hack:相同] 输入：

5
3 1 1
3 2 1
3 1 3
5 9 9
5 8 6

正确输出（例）：

26
5 4

错误输出（例）：

24
4 5

::::

然后第一行输出 dp_n ，接着第二行输出 x 和 y 就可以 AC 啦！

本代码时空复杂度皆为 O(N) 。

::::success[AC 代码]

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

int n;
int a[N],b[N],c[N];

int x,y;
int num;
int dp[N];

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        b[i]-=a[i];
        c[i]-=a[i];
    }

    if(b[1]+c[2]>b[2]+c[1]) x=1,y=2;
    else x=2,y=1;
    dp[2]=a[1]+a[2]+b[x]+c[y];

    for(int i=3;i<=n;i++)
    {
        dp[i]=dp[i-1]-b[x]-c[y]+a[i];
        num=max({b[i]+c[y],b[x]+c[i],
        b[x]+c[y],b[i]+c[x],b[y]+c[i]});
        dp[i]+=num;

        if(num==b[i]+c[y]) x=i;
        else if(num==b[x]+c[i]) y=i;
        else if(num==b[i]+c[x]) y=x,x=i;
        else if(num==b[y]+c[i]) x=y,y=i;
    }

    cout<<dp[n]<<endl;
    cout<<x<<' '<<y<<endl;
    return 0;
}

::::