状态压缩DP SRM 667 Div1 OrderOfOperations 250
|
题意:给n个01串,设计一种顺序,使得每次新出现的1的个数的平方和最小
分析:比赛时不知道是div1的题,以为暴力贪心可以过,结果被hack掉了。题解说没有充分的证明使用贪心是很有风险的,正解是用状态压缩DP。
收获:爆零还能涨分,TC真奇怪。
int dp[(1<<20)+10];
int a[55]; class OrderOfOperations {
public:
int minTime( vector <string> s ) {
int n = s.size (), m = s[0].length ();
memset (a, 0, sizeof (a));
int tot = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (s[i][j] == '1') a[i] |= (1<<j);
}
tot |= a[i];
}
memset (dp, INF, sizeof (dp));
dp[0] = 0;
for (int i=0; i<(1<<m); ++i) {
for (int j=0; j<n; ++j) {
int x = i | a[j]; //从i状态转移到x的状态
int y = x - i; //表示新出现的1
int k = __builtin_popcount (y); //内置函数,快速得到二进制下1的个数
dp[x] = min (dp[x], dp[i] + k * k); //类似Bellman_Ford
}
} return dp[tot];
}
};
最新文章
- 【Java EE 学习 78 上】【数据采集系统第十天】【Service使用Spring缓存模块】
- ubuntu下安装JDK并搭建activeMQ
- oracle xmltype导入并解析Excel数据 (一)创建表与序
- ABAP字符串翻转
- Javascript正则表达式的初步学习
- C++ sort函数
- time_wait 过多 造成网络慢 实战
- ios 添加通用断点定位到异常点
- 第一次写博客,关于前端开发deMVC在js中的应用
- jackson - 生成jason工具-简单示例
- VS2010 express中改变VC Default include/lib/… 目录
- MT【332】椭圆正交变换
- 关于H5页面在iPhoneX适配
- RabbitMQ 分发到多Consumer(Publish/Subscribe)
- Sqoop找不到主类 Error: Could not find or load main class org.apache.sqoop.Sqoop
- caffe中google protobuf使用问题
- 动态规划法(三)子集和问题(Subset sum problem)
- 关于ListBox在Grid中无法充满的问题
- 【Android内存泄漏检测】LeakCanary使用总结
- HDU 2087 剪花布条(字符串匹配,KMP)