[luoguP2915] [USACO08NOV]奶牛混合起来Mixed Up Cows(DP)
2024-09-02 12:48:06
f[i][S] 表示当前集合为 S,最后一个数为 i 的最优解
f[i][S] += f[j][S - i] (j, i ∈ S && j != i && abs(a[i] - a[j]) > k)
——代码
#include <cstdio>
#include <iostream>
#define LL long long int a[];
int n, m, k;
LL ans, f[][ << ]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline int abs(int x)
{
return x < ? -x : x;
} int main()
{
int i, j, S;
n = read();
k = read();
m = ( << n) - ;
for(i = ; i <= n; i++) a[i] = read();
for(i = ; i <= n; i++) f[i][ << i - ] = ;
for(S = ; S <= m; S++)
for(i = ; i <= n; i++)
if(( << i - ) & S)
for(j = ; j <= n; j++)
if(i ^ j && ( << j - ) & S && abs(a[i] - a[j]) > k)
f[i][S] += f[j][( << i - ) ^ S];
for(i = ; i <= n; i++) ans += f[i][m];
printf("%lld\n", ans);
return ;
}
最新文章
- 教你一招:win 7 或win 10右键菜单 添加获取管理员权限
- JavaScript之继承(原型链)
- NGINX下配置404错误页面的方法分享
- Asp.Net Mvc视图引擎Razor介绍
- 关于Windows平台下应用程序加载DLL模块的问题.
- WPF多语言化的实现
- SQL数据库中把一个表中的数据复制到另一个表中
- 如何使用Java、Servlet创建二维码
- antlr 4新特性总结及与antlr v3的不同
- 物理dataguard 正常切换 脚色转换,switchover_status 状态改变
- [Swift]LeetCode706. 设计哈希映射 | Design HashMap
- elephant-bird学习笔记
- 在vim编辑器python实现tab补全功能
- MySQL学习----索引的使用
- for 循环分解
- SpringBoot2.0.2 Application调用的三种方式
- Android逆向进阶(7)——揭开Hook的神秘面纱
- Android 自定义可拖拽View,界面渲染刷新后不会自动回到起始位置
- zabbix server 与数据库不在同一台服务器上面
- VMware快照的工作原理
热门文章
- bzoj 1639: [Usaco2007 Mar]Monthly Expense 月度开支【二分】
- python/shell脚本报异常^M: bad interpreter: No such file or directory
- 同余模定理 HDOJ 5373 The shortest problem
- 【IIS7.5】Asp文件上传限制,加载页面大小限制
- Android 新闻app的顶部导航栏,怎么实现动态加载?
- 使用openssl搭建CA并颁发服务器证书
- AI:IPPR的数学表示-CNN稀疏结构进化(Mobile、xception、Shuffle、SE、Dilated、Deformable)
- 【转】非常好的Java反射例子
- HDU_1114_piggy-bank
- HDU_1176_免费馅饼_16.4.23再做