D - Bags and Coins

思路:我们可以这样构造,最大的那个肯定是作为以一个树根,所以我们只要找到一个序列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 ;
} /*
*/

最新文章

  1. ytu 1064: 输入三个字符串,按由小到大的顺序输出(水题,字符串处理)
  2. PL/SQL中SELECT总结
  3. AMH4.2 虚拟主机面板Tengine版本
  4. Cannot load JDBC driver class &#39;oracle.jdbc.driver.OracleDriver&#39;
  5. Vijos P1067Warcraft III 守望者的烦恼
  6. HTML随笔2
  7. iOS9 系统分享调用(UIActivityViewController)
  8. Linux 命令行输入
  9. python把列表前几个元素提取到新列表
  10. Linux系统下配置网络、JAVA环境,配置tomcat,mysql
  11. 4 Django应用 第3部分(视图部分)
  12. ettercap的使用
  13. 【洛谷P1126】机器人搬重物
  14. 【巷子】---vue项目打包---基本使用---【vue】
  15. 洛谷P2408 不同字串个数 [后缀数组]
  16. 记一次初步Linux提权
  17. firefox 插件 取消认证签名
  18. 新人成长之入门Vue.js弹窗Dialog介绍(二)
  19. web.xml中出现&lt;servlet-name&gt;default&lt;/servlet-name&gt;是什么意思?
  20. MVCC(Multi-Version Concurrency Control)多版本并发控制机

热门文章

  1. CSS3 box-sizing:border-box的好处
  2. webapi框架搭建-数据访问ef code first
  3. Vue入坑教程(一)——搭建vue-cli脚手架
  4. select 的字段为空,给他显示默认值
  5. yum安装_yum命令的相关操作
  6. sql 存储时空格转成问号问题
  7. Request爬取网站(seo.chinaz.com)百度权重的查询结果
  8. Java IO,硬骨头也能变软
  9. PHP 中 int 和 integer 类型的区别
  10. 【Linux】Linux基本命令扫盲【转】