DFS。搜索以棍数为条件循环搜索较好,这样不会超时。
#include <stdio.h>
#include <string.h>
#include <stdlib.h> #define true 1
#define false 0
#define MAXN 70 int alen;
int parts[MAXN];
char visit[MAXN];
int n, m; int dfs(int beg, int cnt, int len) {
int i; if (len == ) {
++cnt;
if (cnt+ == m)
return true; for (i=; i<n; ++i)
if ( !visit[i] )
break; visit[i] = ;
if ( dfs(i+, cnt, alen-parts[i]) )
return true;
visit[i] = ; return false;
} for (i=beg; i<n; ++i) {
if (visit[i] || parts[i]>len)
continue;
if (i && parts[i]==parts[i-] && !visit[i-])
continue;
visit[i] = ;
if ( dfs(i+, cnt, len-parts[i]) )
return true;
visit[i] = ;
} return false;
} int comp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
} int main() {
int sum;
int i; while (scanf("%d", &n)!=EOF && n) {
sum = ;
for (i=; i<n; ++i) {
scanf("%d", &parts[i]);
sum += parts[i];
}
qsort(parts, n, sizeof(int), comp);
m = n+;
while (m > ) {
--m;
if (sum%m)
continue;
alen = sum/m;
if (parts[] > alen)
continue;
memset(visit, , sizeof(visit));
if ( dfs(, , alen) )
break;
}
printf("%d\n", alen);
} return ;
}
【HDOJ】1455 Sticks的更多相关文章
-
【BZOJ】1455 罗马游戏
[算法]可并堆(左偏树) #include<cstdio> #include<algorithm> using namespace std; ; int l[maxn],r[m ...
-
【HDOJ】5203 Rikka with wood sticks
/* 1002 */ #include <iostream> #include <string> #include <map> #include <queue ...
-
【HDOJ】4729 An Easy Problem for Elfness
其实是求树上的路径间的数据第K大的题目.果断主席树 + LCA.初始流量是这条路径上的最小值.若a<=b,显然直接为s->t建立pipe可以使流量最优:否则,对[0, 10**4]二分得到 ...
-
【HDOJ】1518 Square
DFS+剪枝.与HDOJ 1455如出一辙. #include <stdio.h> #include <stdlib.h> #include <string.h> ...
-
【HDOJ】【3506】Monkey Party
DP/四边形不等式 裸题环形石子合并…… 拆环为链即可 //HDOJ 3506 #include<cmath> #include<vector> #include<cst ...
-
【HDOJ】【3516】Tree Construction
DP/四边形不等式 这题跟石子合并有点像…… dp[i][j]为将第 i 个点开始的 j 个点合并的最小代价. 易知有 dp[i][j]=min{dp[i][j] , dp[i][k-i+1]+dp[ ...
-
【HDOJ】【3480】Division
DP/四边形不等式 要求将一个可重集S分成M个子集,求子集的极差的平方和最小是多少…… 首先我们先将这N个数排序,容易想到每个自己都对应着这个有序数组中的一段……而不会是互相穿插着= =因为交换一下明 ...
-
【HDOJ】【2829】Lawrence
DP/四边形不等式 做过POJ 1739 邮局那道题后就很容易写出动规方程: dp[i][j]=min{dp[i-1][k]+w[k+1][j]}(表示前 j 个点分成 i 块的最小代价) $w(l, ...
-
【HDOJ】【3415】Max Sum of Max-K-sub-sequence
DP/单调队列优化 呃……环形链求最大k子段和. 首先拆环为链求前缀和…… 然后单调队列吧<_<,裸题没啥好说的…… WA:为毛手写队列就会挂,必须用STL的deque?(写挂自己弱……s ...
随机推荐
-
【读书笔记】iOS网络-异步请求与运行循环
异步请求需要运行循环.当数据传递到服务器或是被客户端接收时,运行循环用于实现事件与委托对象之间的通信.异步请求在发出时,会在当前线程的运行循环上操作,这个实现细节是很重要的,因为在GCD块中或者是通过 ...
-
SQL Server 获取服务器信息
最近做了一个小工具,里面涉及到一些取SQL Server 服务器信息的一些东西,找了好久,找到一个不错的,贴出来分享. 系统函数 SERVERPROPERTY ( propertyname ) 包含要 ...
-
TCP协议详解
TCP协议详解 一.TCP协议 1.TCP 通过以下方式提供可靠性: · ◆ 应用程序分割为TCP认为最合适发送的数据块.由TCP传递给IP的信息单位叫做报文段. · ◆ 当TCP发出一个报文段后 ...
-
Nginx 调优经验记录
1.2017年连续爆出5.x版本xshell安全问题和intel的cpu设计漏洞 ,此时我就注意到尽量少暴露自己线上使用的工具以及版本.例如:mysql版本,以及缓存层策略,服务器版本等,以下为 隐藏 ...
-
Linux进程-命令行参数和环境列表
命令行参数 在C中,main函数有很多的变种,比如 main(), int main(), int main(int argc, char *argv[]), int main(int argc, c ...
-
【C语言】字节对齐问题(以32位系统为例)
1. 什么是对齐? 现代计算机中内存空间都是按照字节(byte)划分的,从理论上讲似乎对任何类型的变量的访问可以从任何地址开始,但实际情况是在访问特定变量的时候经常在特定的内存地址访问,这就需要各类型 ...
-
Spring IOC AOP的原理 如果让你自己设计IOC,AOP如何处理(百度)
百度的面试官问,如果让你自己设计一个IOC,和AOP,如何设计, 我把IOC的过程答出来了,但是明显不对, (1) IOC 利用了反射,自己有个id,classtype,hashmap,所有的功能都在 ...
-
STM32的AFIO时钟什么时候需要开启
相比于普通单片机,STM32 拥有复杂的时钟系统,相应的控制器称为 RCC(Reset Clock Controller,复位与时钟控制器).每个外设都配备了外设时钟的开关,当我们不使用某个外设时,可 ...
-
Oracle—RMAN完全恢复
一.RMAN完全恢复的相关概念 1.在RMAN完全恢复中主要使用两个命令,一个是restore,另一个是recover. 2.可以在三个级别恢复,数据库,表空间,数据文件. 3.RMAN中应对于各种情 ...
-
AI下载步骤
ai下载地址:https://www.adobe.com/cn/creativecloud/catalog/desktop.html?promoid=PTYTQ77P&mv=other 破解器 ...