A
太牛了。
复读 jiangly 题解。
先把代价除以二。
设 \(f_{i,j}\) 表示以 \(j\) 的代价覆盖前 \(i\) 个点最多还能覆盖多少距离。发现只有 \(f_{i,x},f_{i,x+1},f_{i,x+2}\) 的值是有意义的。其中 \(x\) 为覆盖的最小代价。因为 \(f_{i,x+3}\) 一定不优。不如你到下个点再买一张短时票。
类似于 ddp 一样的，把 \(f_{i,x},f_{i,x+1},f_{i,x+2}\) 计入 dp 状态。设 \(dp_{i,A,B,C}\) 表示当前考虑到了 \(a_i\), \(f_{i,x} = A,f_{i,x+1} = B,f_{i,x+2} = C\) 的方案数。统计答案计数考虑只在每次 \(x\) 增加的时候统计答案。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 1e3 + 10;
const int mod = 1e9 + 7;
int a[MAX];
int f[2][80][80][80];
int g[10];
int pre[MAX];
void solve(){
int n = read();
pre[0] = 1;
for(int i = 1; i <= n; i++){
a[i] = read();
pre[i] = pre[i - 1] * 2 % mod;
}
f[0][0][0][0] = 1;
int ans = 0;
for(int i = 1; i <= n; i++){
for(int A = 0; A <= 75; A++) for(int B = 0; B <= 75; B++) for(int C = 0; C <= 75; C++) f[i & 1][A][B][C] = 0;
for(int A = 0; A <= 75; A++){
for(int B = A; B <= 75; B++){
for(int C = B; C <= 75; C++){
if(!f[(i & 1) ^ 1][A][B][C]) continue;
g[1] = max(0ll, A - (a[i] - a[i - 1])), g[2] = max(0ll, B - (a[i] - a[i - 1])), g[3] = max(0ll, C - (a[i] - a[i - 1])), g[4] = g[5] = g[6] = 0;
for(int j = 1; j <= 6; j++){
if(j + 1 <= 6) g[j + 1] = max(g[j + 1], g[j] + 20);
if(j + 3 <= 6){
g[j + 3] = max(g[j + 3], g[j] + 75);
}
g[j] = max(g[j], g[j - 1]);
}
f[i & 1][g[1]][g[2]][g[3]] = (f[i & 1][g[1]][g[2]][g[3]] + f[(i & 1) ^ 1][A][B][C]) % mod;
int now = 1;
while(!g[now]) now++;
ans = (ans + f[(i & 1) ^ 1][A][B][C] * pre[n - i] % mod * (now - 1) % mod) % mod;
f[i & 1][g[now]][g[now + 1]][g[now + 2]] = (f[i & 1][g[now]][g[now + 1]][g[now + 2]] + f[(i & 1) ^ 1][A][B][C]) % mod;
}
}
}
}
write(ans * 2 % mod), endl;
}
signed main(){
int t = 1;
while(t--) solve();
return 0;
}