首页 > 代码库 > [luoguP2915] [USACO08NOV]奶牛混合起来Mixed Up Cows（DP）

[luoguP2915] [USACO08NOV]奶牛混合起来Mixed Up Cows（DP）

2024-09-26 10:02:39   214人阅读

传送门

 

f[i][S] 表示当前集合为 S，最后一个数为 i 的最优解

f[i][S] += f[j][S - i] (j, i ∈ S && j != i && abs(a[i] - a[j]) > k)

 

——代码

技术分享
 1 #include <cstdio> 2 #include <iostream> 3 #define LL long long 4  5 int a[17]; 6 int n, m, k; 7 LL ans, f[17][1 << 17]; 8  9 inline int read()10 {11     int x = 0, f = 1;12     char ch = getchar();13     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;14     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;15     return x * f;16 }17 18 inline int abs(int x)19 {20     return x < 0 ? -x : x;21 }22 23 int main()24 {25     int i, j, S;26     n = read();27     k = read();28     m = (1 << n) - 1;29     for(i = 1; i <= n; i++) a[i] = read();30     for(i = 1; i <= n; i++) f[i][1 << i - 1] = 1;31     for(S = 1; S <= m; S++)32         for(i = 1; i <= n; i++)33             if((1 << i - 1) & S)34                 for(j = 1; j <= n; j++)35                     if(i ^ j && (1 << j - 1) & S && abs(a[i] - a[j]) > k)36                         f[i][S] += f[j][(1 << i - 1) ^ S];37     for(i = 1; i <= n; i++) ans += f[i][m];38     printf("%lld\n", ans);39     return 0;40 }
View Code

 

[luoguP2915] [USACO08NOV]奶牛混合起来Mixed Up Cows（DP）


联系
我们