Codeforces Round #207 (Div. 1) D - Bags and Coins 构造 + bitset优化dp + 分段查找优化空间
2024-08-24 22:15:57
思路:我们可以这样构造,最大的那个肯定是作为以一个树根,所以我们只要找到一个序列a1 + a2 + a3 .... + ak 并且ak为
所有点中最大的那个,那么我们a1, a2, a3..., ak-1 作为单独的点,其他没有涉及到的点套在ak的里面。
现在问题变成了找出a1, a2, a3, a4, ... , ak。 可以用bitset优化普通dp,因为要找路径,空间开不下,所以需要分段。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, s;
PII a[N];
bitset<> dp[N/];
bitset<> dp2;
bitset<> tmp;
vector<int> edge[N];
vector<PII> dol;
int c[N];
bool in[N]; bool ok(int x, int y) {
if(y < ) return false;
dp2 = dp[x/];
for(int i = x/*+; i <= x; i++)
dp2 |= (dp2 << a[i].fi);
return dp2[y];
} int main() {
scanf("%d%d", &n, &s);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i].fi);
a[i].se = i;
}
sort(a+, a++n);
int tar = s - a[n].fi;
tmp[] = ; dp[] = tmp;
for(int i = ; i < n; i++) {
tmp |= (tmp<<a[i].fi);
if(i % == ) dp[i/] = tmp;
}
if(ok(n-, tar)) {
for(int i = n-, now = tar; i >= ; i--) {
if(now >= a[i].fi && ok(i-, now-a[i].fi)) {
now = now - a[i].fi;
in[a[i].se] = true;
}
}
for(int i = ; i < n; i++) {
if(in[a[i].se]) {
c[a[i].se] = a[i].fi;
} else {
dol.push_back(a[i]);
}
}
dol.push_back(a[n]);
for(int i = ; i < dol.size(); i++) {
if(i) {
c[dol[i].se] = dol[i].fi - dol[i-].fi;
edge[dol[i].se].push_back(dol[i-].se);
} else {
c[dol[i].se] = dol[i].fi;
}
}
for(int i = ; i <= n; i++) {
printf("%d %d ", c[i], edge[i].size());
for(int j : edge[i]) printf("%d ", j);
puts("");
}
} else {
puts("-1");
}
return ;
} /*
*/
最新文章
- ytu 1064: 输入三个字符串,按由小到大的顺序输出(水题,字符串处理)
- PL/SQL中SELECT总结
- AMH4.2 虚拟主机面板Tengine版本
- Cannot load JDBC driver class &#39;oracle.jdbc.driver.OracleDriver&#39;
- Vijos P1067Warcraft III 守望者的烦恼
- HTML随笔2
- iOS9 系统分享调用(UIActivityViewController)
- Linux 命令行输入
- python把列表前几个元素提取到新列表
- Linux系统下配置网络、JAVA环境,配置tomcat,mysql
- 4 Django应用 第3部分(视图部分)
- ettercap的使用
- 【洛谷P1126】机器人搬重物
- 【巷子】---vue项目打包---基本使用---【vue】
- 洛谷P2408 不同字串个数 [后缀数组]
- 记一次初步Linux提权
- firefox 插件 取消认证签名
- 新人成长之入门Vue.js弹窗Dialog介绍(二)
- web.xml中出现<;servlet-name>;default<;/servlet-name>;是什么意思?
- MVCC(Multi-Version Concurrency Control)多版本并发控制机