显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 
 
 
 

HDU 2546 0-1背包问题

2012-10-5 22:53:27 阅读477 评论0 52012/10 Oct5

http://acm.hdu.edu.cn/showproblem.php?pid=2546

背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题。

01背包问题,可以这么理解。

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。


基本思路

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

作者  | 2012-10-5 22:53:27 | 阅读(477) |评论(0) | 阅读全文>>

计算程序运行时间的方法

2011-5-22 17:02:29 阅读322 评论1 222011/05 May22

转自:http://apps.hi.baidu.com/share/detail/15708526

1
这个是windows里面常用来计算程序运行时间的函数;
DWORD dwStart = GetTickCount();
//这里运行你的程序代码
DWORD dwEnd = GetTickCount();
则(dwEnd-dwStart)就是你的程序运行时间, 以毫秒为单位
这个函数只精确到55ms,1个tick就是55ms。

作者  | 2011-5-22 17:02:29 | 阅读(322) |评论(1) | 阅读全文>>

poj 2954 Triangle Pick公式

2011-5-10 10:42:00 阅读228 评论0 102011/05 May10


http://poj.org/problem?id=2954
计算三角内部座标值为整数的点有多少个(不包括边上和顶点的点)。
Pick公式的应用:Area=a/2+b-1;a为边界点,b为内部点。
#include<stdio.h>
#include<stdlib.h>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
    int

作者  | 2011-5-10 10:42:00 | 阅读(228) |评论(0) | 阅读全文>>

poj 2540 Hotter Colder 半平面交 不等式求区域面积

2011-5-9 12:09:35 阅读494 评论0 92011/05 May9

在一个区间内寻找某一个点,每次走法会提示距目标是更近、更远还是相同。每次可确定一个目标必在的区域,求这个区域的面积。
 假定寻找者从A点走到B点,做线段AB的中垂线,取距目标近的那一半。用半平面交即可求该区域。
注意Same时区域面积为0;
若有出现面积为0,则之后的都是0;
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstdlib>

作者  | 2011-5-9 12:09:35 | 阅读(494) |评论(0) | 阅读全文>>

poj 1755 Triathlon 半平面交判断不等式是否有解

2011-5-8 23:52:06 阅读326 评论0 82011/05 May8

http://poj.org/problem?id=1755

有一个全能运动必有要求运动员完成游泳、骑自行车、跑步,三个项目。冠军为最快完成所有项目的运动员。已知每个运动员的三项速度分别为Vi, Ui, Wi 。裁判能够任意的设置三个项目的路程。问对某个运动员能否设定一个让他必羸的路程设置。

当构造一个a,b,c的距离,使得t = a/u + b/v + c/w 时间最小,就可以了
   那么就可以转化成  (1 / u1 - 1 / u2) * a + (1 / v1 - 1 / v2) * b + (1 / w1 - 1 / w2) * c < 0

作者  | 2011-5-8 23:52:06 | 阅读(326) |评论(0) | 阅读全文>>

poj 3384 Feng Shui 半平面交

2011-5-7 23:58:25 阅读262 评论0 72011/05 May7

给定一个多边形,在多边形内放有两个相同的圆,使两个圆尽可能多的覆盖多边形。输出最终两个圆心的位置。
最优的放置方法必定是圆内切于两条边,那么把所有的边向内推移半径R的距离,得到新的多边形(也有可能是一个点或一条直线),求出新多边形相距最远的两个顶点,这两个顶点就是圆心的位置了。

作者  | 2011-5-7 23:58:25 | 阅读(262) |评论(0) | 阅读全文>>

poj 3525 Most Distant Point from the Sea 多边形内切圆

2011-5-7 22:24:44 阅读323 评论0 72011/05 May7

求多边形最大内接圆半径。
半平面交+二分查找:把多边形的每条边向内推R的距离,若变幻之后的仍是一个多边形,说明距离 R太小了,若无边说明R过大。
这边有两个纯几何上的问题,就是如果求直线和平移直线。
一、已知两点求直线ax+by+c=0:
        已知两点为A(x[i],y[i]),B(x[i+1],y[i+1]),取直线上的另外一点C(x,y),则有:
     

作者  | 2011-5-7 22:24:44 | 阅读(323) |评论(0) | 阅读全文>>

poj 1474 Video Surveillance 半平面交

2011-5-6 22:46:27 阅读208 评论0 62011/05 May6

http://poj.org/problem?id=1474

和前面做过的两道一样,又是一题判断多边形是否存在核问题,照样粘贴模板。

点是顺时针给出。

#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
using namespace std;
const double MAX =100000000;
const double pi =acos(-1.0);
const double eps=1e-8;
int m,s;
struct node

作者  | 2011-5-6 22:46:27 | 阅读(208) |评论(0) | 阅读全文>>

和poj3335差不多的题目,都是判断多边形核是否存在问题,只不过这里的点是逆时针给出的,所以模板直接用。
#include<cmath>
#include<algorithm>
using namespace std;

const double MAX =100000000;
const double pi =acos(-1.0);
const double eps=1e-8;

作者  | 2011-5-6 22:07:58 | 阅读(272) |评论(0) | 阅读全文>>

poj 3335 Rotating Scoreboard 半平面交

2011-5-6 21:31:39 阅读535 评论0 62011/05 May6

http://poj.org/problem?id=3335
给定一个多边形,判断是否存在核,点顺时针给出。
半平面交模板直接用。

#include<cmath>
#include<algorithm>
using namespace std;

const double MAX =100000000;
const double pi =acos(-1.0);
const double eps=1e-8;
int m,s;
struct node
{
double x,y; //注意类型
}tr[110],p[110],q[110];

作者  | 2011-5-6 21:31:39 | 阅读(535) |评论(0) | 阅读全文>>

poj 1654 多边形面积计算

2011-5-6 16:06:47 阅读206 评论0 62011/05 May6

http://poj.org/problem?id=1654

简单的多边形面积计算,用叉乘公式即可。

c++提交

#include<stdio.h>
#include<stdlib.h>
int dir[10][2]={{0,0},{-1,-1},{0,-1},{1,-1},{-1,0},{0,0},{1,0},{-1,1},{0,1},{1,1}};
int main()
{
 int cas,i;
 int x1,y1,x2,y2;
 long long area;
 char s[1000005];
 scanf("%d",&cas);

作者  | 2011-5-6 16:06:47 | 阅读(206) |评论(0) | 阅读全文>>

poj 2074 Line of Sight

2011-5-6 12:39:36 阅读235 评论0 62011/05 May6

两条平行线段A,B,之间放有数条做为障碍物的线段,所有线段都平行,求B上能看到整个A的最长区间。
poj 2074 Line of Sight - 某年某月 - zxj015的博客
 求出各个障碍物所对应的不能看到整个A的区间,如上图所示区间[a,b]和区间[c,d],剩下的区间即为可看到整个A的区间,求出最长的就可以了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

作者  | 2011-5-6 12:39:36 | 阅读(235) |评论(0) | 阅读全文>>

http://poj.org/problem?id=1584

给一个多边形,和一个圆形的钉子,判断多边形是否为凸多边形,若为凸多边形判断钉子能否被包含在多边形内。

判断是否为凸多边形:相邻的两条边做叉乘i*(i+1)都大于零(假定顶点为逆时针排序,顺时针反之)则为凸多边形。

判断圆心是否在多边形内:设o为圆心,s1,s2为相邻顶点,若叉乘(s1s2)*(s1o)都大于零则圆心在多边形内部。(假定顶点为逆时针排序,顺时针反之)

之后找圆心到多边形边的最短距离,若最短距离小于圆半径必定不会包含在多边形内。

#include<stdio.h>
#include<stdlib.h>

作者  | 2011-5-5 23:55:58 | 阅读(349) |评论(0) | 阅读全文>>

poj 3449 Geometric Shapes

2011-5-5 20:52:12 阅读230 评论0 52011/05 May5

http://poj.org/problem?id=3449

在平面上给定一些几何图形,求任一个图形会和其它的哪些图形相交。

本题并不难,线段相交判断即可。在求解正方形时,已知正方形的两个对角点(x0,y0),(x2,y2)时可由下面的方程求出(x1,y1),(x3,y3)。

x1 + x3 = x0 + x2;

x1 - x3 = y2 - y0;

y1 + y3 = y0 + y2;

y3 - y1 = x2 - x0;

 

#include<stdio.h>
#include<stdlib.h>

作者  | 2011-5-5 20:52:12 | 阅读(230) |评论(0) | 阅读全文>>

poj 1039 Pipe 直线线段相交判断+枚举

2011-5-5 16:18:01 阅读227 评论0 52011/05 May5

http://poj.org/problem?id=1039
黑书P359例题
题目要我们求出光线在Pipe里能射到的最远处的x坐标。我们只要找出其中一条最优光线。
一条最优光线必须满足的一个必要条件是:它必定过Pipe的一个上顶点和一个下顶点。否则,我们总可以通过平移或是旋转使光线走更远的距离。有了这个条件,就可以通过枚举所有的上下顶点对(i,j),找出最优的。
过上下顶点的光线共有n*n条,要求的就是
Max{X(i,j) | 过上下顶点对(i,j)能达到的最远距离的横坐标} (i=0..n-1,j=0..n-1;)

作者  | 2011-5-5 16:18:01 | 阅读(227) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 
 
 

福建省 福州市 双鱼座

 发消息  写留言

 
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注