DAG上的动态规划

时间:2022-06-28 22:44:17

嵌套矩形问题(最长路及其字典序)
有n个举行,选出尽量多的矩阵排成一排,使得除了最后一个之外,每一个矩形可以嵌套在下一个矩形内,并且打印

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <map>
#include <set> using namespace std; const int INF = 0xffffff;
const double esp = 10e-;
const double Pi = * atan(1.0);
const int maxn = + ;
const long long mod = ;
const int dr[] = {,,-,,-,,-,};
const int dc[] = {,,,-,,-,-,};
typedef long long LL; LL gac(LL a,LL b){
return b?gac(b,a%b):a;
}
int n;
bool graph[maxn][maxn];
struct G{
int a,b;
};
G g[maxn];
int d[maxn][maxn];
bool judge(int x,int y){
if(g[x].a < g[y].a && g[x].b < g[y].b)
return ;
if(g[x].a < g[y].b && g[x].b < g[y].a)
return ;
return ;
}
int dp(int i,int tt){
if(d[tt][i] > )
return d[tt][i];
d[tt][i] = ;
for(int j = ;j <= n;j++){
if(graph[i][j]){
d[tt][i] = max(d[tt][i],dp(j,tt)+);
}
}
return d[tt][i];
}
void print_ans(int i,int tt){
printf("%d ",i);
for(int j = ;j <= n;j++){
if(graph[i][j] && d[tt][i] == d[tt][j] + ){
print_ans(j,tt);
break;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
// freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = ;i <= n;i++){
getchar();
char ch;
scanf("%c%d%d",&ch,&g[i].a,&g[i].b);
//int fin = -1;
for(int j = ;j < i;j++){
if(judge(i,j)){
graph[i][j] = ;
}
if(judge(j,i)){
graph[j][i] = ;
}
}
}
int ans = -;
int m;
memset(d,,sizeof(d));
for(int i = ;i <= n;i++){
int tmp = dp(i,i);
if(tmp > ans){
m = i;
ans = tmp;
}
}
printf("%d\n",ans);
print_ans(m,m);
}
return ;
}

硬币问题

有n种硬币,面值分别为v1,v2,v3……给定非负整数s问选用多少个硬币使面值恰好等于s?求出硬币数目最大值和最小值……

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <map>
#include <set> using namespace std; const int INF = 0xffffff;
const double esp = 10e-;
const double Pi = * atan(1.0);
const int maxn = + ;
const long long mod = ;
const int dr[] = {,,-,,-,,-,};
const int dc[] = {,,,-,,-,-,};
typedef long long LL; LL gac(LL a,LL b){
return b?gac(b,a%b):a;
}
int V[maxn];
int minv[maxn];
int maxv[maxn];
int d[maxn];
int n;
int dp(int i){
if(d[i] != -)
return d[i];
d[i] = -INF;
for(int j = ;j <= n;j++){
if(i >= V[j]){
d[i] = max(d[i],dp(i - V[j])+);
}
}
return d[i];
}
void print_ans(int * a,int s){
for(int i = ;i <= n;i++){
if(s >= V[i] && a[s] == a[s -V[i] ]+){
printf("%d ",V[i]);
print_ans(a,s-V[i]);
break;
}
}
}
void print_Ans(int *a,int s){
while(s){
printf("%d ",a[s]);
s -= a[s];
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
// freopen("output.txt","w",stdout);
#endif
while(~scanf("%d",&n)){
int s;
scanf("%d",&s);
for(int i = ;i <= n;i++){
scanf("%d",&V[i]);
}
d[] = ;
for(int i = ;i <= s;i++)
d[i] = -;
minv[] = maxv[] = ;
for(int i = ;i <= s;i++){
minv[i] = INF;
maxv[i] = -INF;
}
int min_coin[maxn];
int max_coin[maxn];
for(int i = ;i <= s;i++){
for(int j = ;j <= n;j++){
if(i >= V[j]){
if(minv[i] > minv[i - V[j]]+){
minv[i] = min(minv[i],minv[i-V[j] ] + );
min_coin[i] = V[j];
}
if(maxv[i] < maxv[i-V[j] ]+){
maxv[i] = max(maxv[i],maxv[i -V[j] ]+);
max_coin[i] = V[j];
}
minv[i] = min(minv[i],minv[i-V[j] ] + );
maxv[i] = max(maxv[i],maxv[i -V[j] ]+);
}
}
}
print_Ans(min_coin,s);
printf("\n");
print_Ans(max_coin,s);
printf("\n");
printf("%d %d\n",minv[s],maxv[s]);
print_ans(minv,s);
printf("\n");
print_ans(maxv,s);
printf("\n");
int ans = dp(s) ;
if(ans < -){
printf("no problem\n");
}
else{
printf("%d\n",ans);
}
}
return ;
}

DAG上的动态规划的更多相关文章

  1. UVa 103 Stacking Boxes --- DAG上的动态规划

    UVa 103 题目大意:给定n个箱子,每个箱子有m个维度, 一个箱子可以嵌套在另一个箱子中当且仅当该箱子的所有的维度大小全部小于另一个箱子的相应维度, (注意箱子可以旋转,即箱子维度可以互换),求最 ...

  2. DAG上的动态规划之嵌套矩形

    题意描述:有n个矩形,每个矩形可以用两个整数a.b描述,表示它的长和宽, 矩形(a,b)可以嵌套在矩形(c,d)当且仅当a<c且b<d, 要求选出尽量多的矩形排成一排,使得除了最后一个外, ...

  3. UVA 1025 &quot&semi;A Spy in the Metro &quot&semi; (DAG上的动态规划?? or 背包问题??)

    传送门 参考资料: [1]:算法竞赛入门经典:第九章 DAG上的动态规划 题意: Algorithm城市的地铁有 n 个站台,编号为 1~n,共有 M1+M2 辆列车驶过: 其中 M1 辆列车从 1 ...

  4. 第九章(二)DAG上的动态规划

    DAG上的动态规划: 有向无环图上的动态规划是学习DP的基础,很多问题都可以转化为DAG上的最长路.最短路或路径计数问题. 1.没有明确固定起点重点的DAG模型: 嵌套矩形问题:有n个矩形,每个矩形可 ...

  5. DAG 上的动态规划(训练指南—大白书)

    有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础.很多问题都可以转化为DAG上的最长路.最短路或路径计数问题. 一.矩形嵌套 题目描述:       ...

  6. DP入门(2)——DAG上的动态规划

    有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础.很多问题都可以转化为DAG上的最长路.最短路或路径计数问题. 一.DAG模型 [嵌套矩形问题] 问题 ...

  7. 嵌套矩形——DAG上的动态规划

    有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础.非常多问题都能够转化为DAG上的最长路.最短路或路径计数问题. 题目描写叙述: 有n个矩形,每一个矩 ...

  8. DAG上的动态规划---嵌套矩形(模板题)

    一.DAG的介绍 Directed Acyclic Graph,简称DAG,即有向无环图,有向说明有方向,无环表示不能直接或间接的指向自己. 摘录:有向无环图的动态规划是学习动态规划的基础,很多问题都 ...

  9. UVA 437 The Tower of Babylon(DAG上的动态规划)

    题目大意是根据所给的有无限多个的n种立方体,求其所堆砌成的塔最大高度. 方法1,建图求解,可以把问题转化成求DAG上的最长路问题 #include <cstdio> #include &l ...

  10. The Tower of Babylon UVA - 437 DAG上的动态规划

    题目:题目链接 思路:每个方块可以用任意多次,但因为底面限制,每个方块每个放置方式选一个就够了,以x y为底 z 为高,以x z为底 y 为高,以y z为底 x为高,因为数据量很小,完全可以把每一种当 ...

随机推荐

  1. Thinkphp3&period;2&period;3 执行query命令 包括在模板中使用&lt&semi;php&gt&semi; &lt&semi;&sol;php&gt&semi;时 query的使用方法

    $sql="select * from `rjshop_productbase` where `id`=1"; $Model =M();$query=$Model->quer ...

  2. JS 工厂模式

    1.什么是工厂模式 工厂模式是面向对象的设计模式,作用在于创建一个对象,mixin模式也是面向对象的设计模式,作用在于继承. 工厂模式定义一个接口,让实现这个接口的类来决定实例化哪个类,也就是说通过一 ...

  3. Sharepoint页面项目展示画廊纯前端实现,后端用list&sol;library简单维护

    需求背景: Sharepoint页面项目展示画廊.图片+文字,要求图片与文字用Sharepoint Library维护,然后在sharepoint页面上被调用,生成项目展示画廊. 解决方案(纯前端), ...

  4. MEF入门之不求甚解,但力求简单能讲明白&lpar;三&rpar;

    上一篇我们已经获得了制定类型的实例,但我们还无法对其进行有效的控制. 我们用ExportMetadata属性可以对具体的某个实例做标记,相当于命名.这么理解不知道对否. 在IPart项目中添加一个接口 ...

  5. 智能车学习(十二)&mdash&semi;&mdash&semi;智能车原理

    一.直立行走任务分解 1.任务分解 (1) 控制车模平衡:通过控制两个电机正反向运动保持车模直立平衡状态 (2) 控制车模速度:通过调节车模的倾角来实现车模速度控制,实际上最后还是演变成通过控制电机的 ...

  6. curl转让query string逃生参数

    假设curl访问http网站.传递参数.需要使用\如&字首. 例: http://myjenkins/job/run_schedule/buildWithParameters?token=fe ...

  7. python3&period;7之12306抢票脚本实现

    悲催的12306,彻底沦为各路抢票软件的服务提供方.元旦伊始,纯粹12306官网及APP抢票,愈一周的时间,仅到手一张凌晨3:55回家的站票.为远离脑残,无奈选择抢票软件,预购年后返沪车票.BTW,研 ...

  8. mycql 多表联合查询

    egon笔记: 1 单表查询 select distinct 字段1,字段2,字段3 from 表 where 约束条件 group by 分组字段 having 过滤条件 order by 排序字段 ...

  9. JS中的&OpenCurlyDoubleQuote;&equals;&equals;”符号及布尔值转换规则

    what are the rules for how == converts types? 关于"=="的比较规则: 1. Comparing numbers and string ...

  10. 2018&period;06&period;30 cdq分治

    #cdq分治 ##一种奇妙的分治方法 优点:可以顶替复杂的高级数据结构:常数比较小. 缺点:必须离线操作. CDQ分治的基本思想十分简单.如下: 我们要解决一系列问题,包含修改和查询操作,我们将这些问 ...