题解归档 - cf2229G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229G
• 本地来源：problems/cf2229G/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/G
• 原始标题：cf2229G

思路

cf2229G

status: blocked / needs a stronger interval DP.

pattern: time-dependent path graph, max-plus DP, large horizon.

claim tested: Going directly toward the final best house and waiting only on that path is false.

counterexample:

1
3 4 2
9 1 2
3 1

The direct-left plan gets 20, but the optimal route is day1 2->3, day2 3->2, day3 2->1, day4 stay at 1, total 2+1+9+9=21.

brute/check: brute.cpp does exact day-by-day DP for small k; gen.cpp generates small random instances. This should be used to check any future formula.

next: Need a compressed-time / interval-component max-plus structure. Between road-build days, active roads form intervals; a gap update is a static path transition for many days. The hard part is summarizing each interval so that merges can be processed without O(nk).

代码

来源：problems/cf2229G/solution.cpp

/* Author: likely
 * Time: YYYY-MM-DD HH:MM:SS
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5];
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>s[i];
    }
    return 0;
}