题目链接:uva 1377 - Ruler
题目大意:给出一些刻度,要求制作一把尺子,可以直接测量出给出的刻度,要求尺子尽量短,并且刻度尽量少,注意:所标记的刻度数不会大于7,题目限制。
解题思路:注意题目中的限制,说刻度数最大为7,C(2,7) = 21,也就是说最多能表示21个长度,题目所给出的50个长度有一半多式重复的长度。让后题目还有一个限制条件,说尺子尽量短,也就是说最大的刻度要尽量小(因为所标的刻度不一定是给出刻度的某一个,例5 7 8 10 100)。我的做法是广搜,每个一个状态记录已选刻度,可表达的刻度(二进制),每次添加第一个不能测量的长度。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const int N = 50;
const int M = 100005;
typedef set<int>::iterator iter;
struct state {
int s, now;
set<int> rec;
}ans;
int n, c, d[N], v[M];
void init() {
c = 0;
ans.rec.clear();
memset(v, 0, sizeof(v));
int a;
for (int i = 0; i < n; i++) {
scanf("%d", &a);
if (!v[a]) {
d[c++] = a;
v[a] = 1;
}
}
sort(d, d + c);
memset(v, -1, sizeof(v));
for (int i = 0; i < c; i++) v[d[i]] = i;
}
bool cmp(state a, state b) {
if (a.rec.size() != b.rec.size()) return a.rec.size() > b.rec.size();
iter p = a.rec.begin(), q = b.rec.begin();
while (p != a.rec.end()) {
if (*p != *q) return *p > *q;
p++; q++;
}
return false;
}
state add(state u, int k) {
for (iter i = u.rec.begin(); i != u.rec.end(); i++) {
int t = abs(*i - k);
if (v[t] == -1) continue;
if ((u.s & (1<<v[t])) == 0) u.s += (1<<v[t]);
}
u.rec.insert(k);
return u;
}
void bfs() {
int tmp = (1 << c) - 1, m = d[c-1];
state u;
queue<state> que;
u.s = 0; u.rec.insert(0);
que.push(u);
while (!que.empty()) {
u = que.front(); que.pop();
if (ans.rec.size() != 0 && ans.rec.size() < u.rec.size()) return;
if (u.s == tmp) {
if (ans.rec.size() == 0 || cmp(ans, u)) ans = u;
} else {
if (u.rec.size() == 7) continue;
for (int i = 0; i < c; i++) if ((u.s & (1<<i)) == 0) {
for (iter j = u.rec.begin(); j != u.rec.end(); j++) {
if (*j + d[i] <= m) que.push(add(u, *j + d[i]));
if (*j > d[i]) que.push(add(u, *j - d[i]));
}
break;
}
}
}
}
void solve() {
bfs();
int flag = false;
printf("%lu\n", ans.rec.size());
for (iter i = ans.rec.begin(); i != ans.rec.end(); i++) {
if (flag) printf(" ");
printf("%d", *i); flag = true;
}
printf("\n");
}
int main() {
int cas = 1;
while (scanf("%d", &n) == 1 && n) {
init();
printf("Case %d:\n", cas++);
solve();
}
return 0;
}
分享到:
相关推荐
e-ruler 网页测量工具 可以测量两点之间距离,多点之间距离,测量角度,显示起点和终点的坐标值
slide-ruler二次封装后的组件
E-Ruler E-尺是一个用来测量的工具软件,可以用来测量屏幕上两点或多点的距离和角度,特别适合从事网页或美工工作的您
学MFC的初级源码---Ruler.h.doc 学MFC的初级源码---Ruler.h.doc
Chrome浏览器一款强大前端学习必备工具的插件,用于网页尺寸测量,取色,它可以指定测量各个div间的距离,也可以测定div中各个零件的大小尺寸
import Ruler from 'react-native-animated-ruler' ; < Ruler xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed> alert ( value ) } minimum = { 10 } maximum = { 80 } ...
Page-Ruler是一个可以让你在任何页面都可以随意画出一个可以测量任何元素尺寸和位置的小插件。Page-Ruler不仅仅可以测量元素的宽度和高度,同时可以测出元素所相对于页面的绝对位置,对于前端狗们来说,这应该算是个...
微信小程序尺子,方便测量simple-ruler-master.zip
var SwipeRuler = require ( 'react-swipe-ruler' ) ; var React = require ( 'react' ) ; var ReactDOM = require ( 'react-dom' ) ; ReactDOM . render ( < SwipeRuler> , container ) ; 原料药 道具 名称 类型 ...
page-ruler, Google Chrome的页面标尺扩展 ,感谢你的Fish我一直致力于维护 Page,因此我没有花时间把所有权转移给另一个人,希望它能永久地取代 stagnating 。我希望对每个安装扩展的人感谢,特别是那些提供新特性...
刻度通过指定屏幕分辨率和显示器点距来校准DPI,与实际长度吻合得很好,或者可以通过标准实物(A4纸、通用卡片、光盘等)来校准
Privacy Friendly Ruler Privacy Friendly Ruler turns the phone screen into a ruler for quick measurments on the go. This app is optimized regarding the user's privacy. It doesn't use any tracking ...
带网格的拖拽特效。并且有标尺。类似于ps的的标尺。标尺插件用的ruler。
ruler,尺子,刻度尺,设置身高,体重
Page-Ruler是一款可以测量Chrome浏览器中网页元素大小尺寸的谷歌浏览器插件,简单易用,推荐尝试尝试
京东数据中台组件
glsl-ruler 受启发的调试光线跟踪SDF的帮助器模块在上的。 感谢 :sparkles:用法trace = require(glsl-ruler/trace, , ) 当前, glsl-ruler需要代表您处理光线跟踪–它使用与非常相似的API进行。 有关更多详细信息,...
var ruler = require ( 'page-ruler' ) ; 用 可以使用以下方法: ruler . document ( ) ; // Returns { width, height } object ruler . documentWidth ( ) ; ruler . documentHeight ( ) ; ruler . viewport ( )...
一款PCB直尺,可3D查看,可直接送厂打板,自行改丝印。只包含PCB文件,长度25厘米,切换mil。背面有常用元器件封装和过线载流大小、过孔大小,常用贴片元器件封装
simple-ruler 微信小程序,简单尺子 当想要量一个物品时,但手边没有尺子,可以打开“简单尺子”小程序用手机测量。 “简单尺子”小程序是使用小程序的 canvas 接口进行绘制的,目前在小程序中没有找到毫米(mm)和...