JZOJ 1340 周长

发表于 | 分类于 |

首先看数据范围，根据套路优先考虑状压 DP。

周长本质上只需要求相邻的高度之差加上边缘两条的高度和所有宽（即 \(2n\)）。

设 \(f_{S,i}\) 表示已使用的农田的编号集合为 \(S\)，排出来最后一个农田的编号是 \(i\)。
那么有转移显然（

对于方案数，同时开另一个数组在 DP 转移时更新即可。

代码： 

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
31
32
33
34
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 15;
const int C = 100;
int n,full,a[N + 5];
int f[(1 << N) + 5][N + 5];
long long g[(1 << N) + 5][N + 5];
int ans;
long long tot;
int main()
{
    memset(f,-0x3f,sizeof f);
    scanf("%d",&n),full = (1 << n) - 1;
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),f[1 << i - 1][i] = a[i],g[1 << i - 1][i] = 1;
    for(register int i = 0;i <= full;++i)
        for(register int j = 1;j <= n;++j)
            if(i & (1 << j - 1))
                for(register int k = 1;k <= n;++k)
                    if(!(i & (1 << k - 1)))
                        if(f[i][j] + abs(a[j] - a[k]) > f[i | (1 << k - 1)][k])
                            f[i | (1 << k - 1)][k] = f[i][j] + abs(a[j] - a[k]),g[i | (1 << k - 1)][k] = g[i][j];
                        else if(f[i][j] + abs(a[j] - a[k]) == f[i | (1 << k - 1)][k])
                            g[i | (1 << k - 1)][k] += g[i][j];
    for(register int i = 1;i <= n;++i)
        if(f[full][i] + 2 * n + a[i] > ans)
            ans = f[full][i] + 2 * n + a[i],tot = g[full][i];
        else if(f[full][i] + 2 * n + a[i] == ans)
            tot += g[full][i];
    printf("%d %lld\n",ans,tot);
}