JZOJ 6485 沙塔斯月光

发表于 | 分类于 |

实际上看到第三个操作类似二阶前缀和就有考虑过提前计算贡献之类的，可惜没有想到（

正着倒着都能做。
这里倒着做。

设 \(f_{i,j,k}\) 表示考虑了 \(i \ldots n\) 的阶段，用了 \(j\) 次治愈法术，所有用治愈法术的阶段编号之和为 \(k\)。
则考虑三种操作有 \[ f_{i,j,k} = \max\{f_{i+1,j-1,k-i} + x_i, f_{i+1,j,k} + y_i \cdot j, f_{i+1,j,k} + z_i \cdot (k - i \cdot j)\} \]

答案显然为 \(\max\limits_{i,j} f_{1,i,j}\)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 80;
int T,n;
int a[N + 5][3];
long long f[N + 5][N + 5][N * (N + 1) / 2 + 5],ans;
int main()
{
    freopen("fortune.in","r",stdin),freopen("fortune.out","w",stdout);
    scanf("%*d%d",&T);
    for(;T;--T)
    {
        scanf("%d",&n),ans = -0x3f3f3f3f3f3f3f3f;
        for(register int i = 1;i <= n;++i)
            scanf("%d%d%d",a[i],a[i] + 1,a[i] + 2);
        memset(f,-0x3f,sizeof f),f[n + 1][0][0] = 0;
        for(register int i = n;i;--i)
            for(register int j = 0;j <= n - i + 1;++j)
                for(register int k = 0,r = (i + n) * (n - i + 1) / 2;k <= r;++k)
                    j > 0 && k >= i && (f[i][j][k] = max(f[i][j][k],f[i + 1][j - 1][k - i] + a[i][0])),
                    f[i][j][k] = max(f[i][j][k],f[i + 1][j][k] + (long long)a[i][1] * j),
                    f[i][j][k] = max(f[i][j][k],f[i + 1][j][k] + (long long)a[i][2] * (k - i * j));
        for(register int i = 0;i <= n;++i)
            for(register int j = 0,r = n * (n + 1) / 2;j <= r;++j)
                ans = max(ans,f[1][i][j]);
        printf("%lld\n",ans);
    }
}