JZOJ 1340.周长

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

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

fS,if_{S,i} 表示已使用的农田的编号集合为 SS,排出来最后一个农田的编号是 ii
那么有转移显然(

对于方案数,同时开另一个数组在 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);
}