题意:给出几个多维的箱子,如果箱子的每一边都小于另一个箱子的对应边,那就称这个箱子小于另一个箱子,然后要求能够套出的最多的箱子。
要注意的是关系图的构建,对箱子的边排序,如果分别都小于另一个箱子就说明是箱子小于,重载<即可。
然后就是正常的dp最长路的搜索了。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: uva103.cpp
* Create Date: 2013-09-12 19:32:36
* Descripton: dp
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100;
struct Box {
int dem;
int e[30];
void Sort() {
sort(e, e + dem);
}
bool operator < (const Box& a) const {
for (int i = 0; i < dem; i++)
if (e[i] >= a.e[i])
return false;
return true;
}
} b[MAXN];
int big[MAXN][MAXN], k, t;
int dp[MAXN];
int solve(int i) {
if (dp[i] > 0) return dp[i];
dp[i] = 1;
for (int j = 0; j < t; j++)
if (big[i][j])
dp[i] = max(dp[i], solve(j) + 1);
return dp[i];
}
void output(int i) {
for (int j = 0; j < t; j++)
if (big[i][j] && dp[i] == dp[j] + 1) {
printf(" %d", j + 1);
output(j);
break;
}
}
int main() {
while (scanf("%d%d", &t, &k) != EOF) {
for (int i = 0; i < t; i++) {
for (int j = 0; j < k; j++) {
b[i].dem = k;
scanf("%d", &b[i].e[j]);
}
b[i].Sort();
}
memset(big, 0, sizeof(big));
memset(dp, 0, sizeof(dp));
for (int i = 0; i < t; i++)
for (int j = 0; j < t; j++)
if (i != j && b[i] < b[j])
big[i][j] = 1;
for (int i = 0; i < t; i++)
solve(i);
int tt = 0;
for (int i = 0; i < t; i++)
if (dp[i] > dp[tt])
tt = i;
printf("%d\n", dp[tt]);
printf("%d", tt + 1);
output(tt);
printf("\n");
}
return 0;
}
分享到:
相关推荐
利用Stacking针对北京市pm2.5数据进行回归预测,直接运行
1012-Stacking Cylinders
利用InSAR Stacking技术监测雷州半岛沉降 ,杜亚男,冯光财,由于长利用InSAR Stacking技术监测雷州半岛沉降期过量开采地下水,雷州半岛出现了大范围的地面沉降,并伴有地裂缝、坍塌等地质灾害,�
IDL批量实现影像多单波段合成LayerStacking,并进行滤波SavitzkyGolayFilter,然后再拆分为单波段
将概念相似度的计算问题看做分类问题,提出一种基于Stacking方法的多策略本体映射框架;利用Stacking方法组合多种概念相似度算法,进而提出基于Widrow-Hoff理论的元数据分类算法LMSMC。该框架中,第0层分类器使用...
html 7 stacking level, 编写html分块,stacing level
针对传统时序分析方法不适用于监测大量级形变的问题,采用Stacking InSAR方法对沛北矿区地表沉降进行监测。与传统的永久散射体技术相比,Stacking InSAR方法具有可监测大量级形变、提高信噪比的优点。
https://github.com/echohandsome制作两层stacking结构理解留出法回顾交叉验证法回顾Stacking集成学习方法介绍留出法回顾
本文来自于博客园,本文主要使用机器学习算法来将个体机器学习器的结果结合在一起,这个方法就是Stacking,希望对您的学习有所帮助。 Ensemblelearning中文名叫做集成学习,它并不是一个单独的机器学习算法,而是将...
一种适用于卷积神经网络的Stacking算法.pdf
为此,提出一种基于极限梯度提升(XGBoost)与Stacking模型融合的短期母线负荷预测方法。基于XGBoost建立多个母线负荷预测元模型,组合构成Stacking模型融合的元模型层,连接一个XGBoost模型对元模型进行融合,整体...
利用ENVI进行图层融合代码
本文来自于csdn,本文是基于《kaggle比赛集成指南》来进行总结的概述什么是集成学习,以及目前较为常用的技术。集成方法是指由多个弱分类器模型组成的整体模型,我们需要研究的是:①弱分类器模型的形式②这些弱分类...
标准化降水蒸散发指数 matlab的代码(Standardized index precipitation evaporation for matlab),直接按照例子中的数据格式运行SPEI_Cal.m文件,运行结果在stacking中查询,可以自己修改时间尺度,亲测可用。
IDL批量实现影像多单波段合成LayerStacking,并进行滤波SavitzkyGolayFilter,然后再拆分为单波段
高光谱图像分类研究中,集成学习能够显著地提高分类效果。但是传统的并行多分类系统对基础分类器有较高要求,即要求差异性及分类均衡。为了解决这一问题,采用Stacking Learning的堆栈式学习方式,首先使用
基于加权Stacking集成学习的Tor匿名流量识别方法.docx
Stacking集成学习在销售预测中的应用.docx
算法模型的融合,使用xgboost,ligbm等继承学习进行融合
Cortex-M4F的Lazy Stacking特性在RTOS上下文切换中的作用