yangliuy
- 浏览: 66169 次
- 性别:
- 来自: 北京
-
最新评论
文章列表
算法分析：先对木棍结构体数组按照l排序，消除一个变量的干扰，然后再找w连续上升的子序列。用临时变量temp，遇到更大的作更新，且标记为0，采用贪心策略去找有几个连续上升的子序列
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct stick{
int l;
int w;
}stick;
int cmp(const void *a,const void *b)
{
if((*(stick *)a).l==(*(stick *)b).l)
...
- 2010-12-09 20:41
- 浏览 705
- 评论(0)
首先自我检讨一下，最近忙一些杂事导致OJ与红宝进度严重滞后，今后要学会专注，回避一些不必要的事情。
为了准备12日的校赛做了这题，动态规划，在网上看到的很经典的解法摘录如下：
l题目分析：
将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3和直线1和直线2最多有两个交点......直线n和其他n-1条直线最多有n-1个交点,由此得出n条直线互不平行且无三线共点的最多交点数:
max=1+2+...+(n-1)=n(n-1)/2;设数组g[1..max],g[i]=0;//交点数i不存在g[i]=1;//交点数i存在(0<=i<=max)m条直线的交点方案数=( ...
- 2010-12-08 21:46
- 浏览 509
- 评论(0)
今天总算上完一门课了，以后做OJ的时间可以渐渐多一些。好几天疲于奔命，OJ也没写几题，囧。今天补起来，补一篇处女博!
这题很简单，但是第一次做的时候没有排序采用暴力判断超时，后来想到先排序再判断更快。
#include <iostream>
using namespace std;
struct mon{
int x;
int y;
};
//按照x y升序排列，如果不排序直接判断容易超时
int cmp(const void *a,const void *b)
{
mon *p1=(mon *)a;
mon *p2=(mo ...
- 2010-12-04 21:40
- 浏览 394
- 评论(0)
第一道背包问题，0-1背包，参考网上一位大牛写的做的。状态方程：dp[i][w] = max{dp[i-1][w], dp[i-1][w-obj[i].wei] + obj[i].val]}，但这样会超内存，需要一个空间复杂度的优化将dp改为一维，这招看来以后得常用，具体见转载的《背包九讲》。
明天好好读读《背包九讲》，在多做几道dp变形题，练习在于精不在多。
#include <iostream>
using namespace std;
const int mMax = 3500;//待选物品个数
const int nMax = 14000;//最大容量
str ...
- 2010-11-30 23:57
- 浏览 516
- 评论(0)
这题是水题，主要是用到了C++字符串和cmath中的pow函数。
最近课程有点多，做POJ时间不够，还是要抓紧一些，尤其是动态规划、搜索题等要多练。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
string s;
while(1){
cin>>s;
if (s == "0")
break;
long result = 0;
int k = 1; ...
- 2010-11-30 22:24
- 浏览 556
- 评论(0)
今天主要是学习了一下DP，三个使用前提：最优子结构、子问题重叠性、无后效性，今后重点练dp题，至少做30题加深理解
这题纯粹为了练习编码速度。
#include <iostream>
#include <string>
using namespace std;
int main(){
int c,miles = 0;
string a;
char b;
while(cin>>a && a[0] != '#'){
if (a[0] != '0')
{
cin>>a>>c ...
- 2010-11-28 21:33
- 浏览 545
- 评论(0)
这题很简单，可以设置结构体保存三维及姓名，求出体积最大的人和最小的人输出即可。
由于没有注意输出"."而贡献了一次WA，囧
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct stu{
stu(){}
string name;
int d;
}s[1000];
int comp(const void * a,const void * b){
return ((stu*)a)-> ...
- 2010-11-27 20:47
- 浏览 556
- 评论(0)
这题想了很久，是经典的动态规划问题，感觉有点难度，在网上看了很多讨论。
看了动态规划还要好好加强。
#include <iostream>
using namespace std;
int main()
{
long i,j,k,l,n,m,t1,maxf,count;
long p[210],d[210],f[210],s[210];
long can[30];
long res[30][1000],from[30][1000];
count=0;
cin>>n>>m;
...
- 2010-11-27 19:56
- 浏览 427
- 评论(0)
这题很简单，直接贴AC代码了
#include <iostream>
#include <string.h>
#define MAXN 10000
using namespace std;
int num[MAXN];
int dnum(int i){
int sum = i;
int temp;
while (i > 0)
{
temp = i%10;
sum += temp;
i = (i-temp)/10;
}
return sum;
}
int main(){
int i,j;
for (i ...
- 2010-11-27 16:24
- 浏览 398
- 评论(0)
在输入的同时，进行一次DP，计算出从左到右的最大值，并把它保存在数组dp的对应的下标元素中，这样之后，对于下标为i的元素，它其中保存的便是前面所有元素可能的最大连续和。再从右到左进行一次DP，计算从右到左的最大连续和。假设此时已经算到下标为i的元素，那么将sum+dp[i-1]与ans进 行比较，将ans取较大者。最后当i到2的时候ans中的值即为所求的最大值。
#include <iostream>
using namespace std;
int dp[100001],num[100001];
const int MINNUM = -99999999;
int ma ...
- 2010-11-27 15:31
- 浏览 530
- 评论(0)
这题很简单，但由于审题不清WA了很多次，太不应该
Any non-alphabetical character should remain the same, and all alphabetical characters will be upper case.
即只要不是字母就不变，
如下写法错误
if(*it == ' ' || *it == ',') continue;
另外，对C++ String的使用中如何将空格也输入也是一个难点，getline不太好用，这里用了一个C的string作为中间量，借助C函数gets完成
#include <iostream>
# ...
- 2010-11-26 17:06
- 浏览 506
- 评论(0)
之所以抛弃char*的字符串而选用C++标准程序库中的string类，是因为他和前者比较起来，不必担心内存是否足够、字符串长度等等，而且作为一个类出现，他集成的操作函数足以完成我们大多数情况下(甚至是100%)的需要。我们可以 ...
- 2010-11-26 16:07
- 浏览 428
- 评论(0)
此题把题意弄懂后就很容易，S顺时针走，E逆时针走，确定一个分割点该处两人相遇时途经的客人数之和相等，直接枚举。
#include <iostream>
using namespace std;
//s顺时针走，e逆时针走，问他们在哪里相遇时路径上面经过的数字之和相等
//直接用枚举法
int main(){
int table[32];
int n,sum1,sum2,i,j;
while(cin>>n,n!=0){
for (i = 1;i <= n;i++)
cin>>table[i];
for (i = ...
- 2010-11-25 23:22
- 浏览 462
- 评论(0)
首先自己练习了一下实现dijkstra算法，可以把dj算法与prim算法对比记忆,要理解pre数组、min数组、V标记数组的含义！
//单源最短路径,dijkstra算法,邻接阵形式,复杂度O(n^2)
//求出源s到所有点的最短路经,传入图的顶点数n,(有向)邻接矩阵mat
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
//可以把dj算法与prim算法对比记忆,要理解pre数组、min数组、V标记数组的含义！
#include <iostream>
#define MAX ...
- 2010-11-25 22:30
- 浏览 354
- 评论(0)
做算法和作技术哪个难? 都很难, 没有可比性. 但是算法做得好的可以转行做技术, 技术做得好的想转行做算法却很困难.我是08年下半年将近期末的时候加入华理ACM队的. 我高中的时候没有编程经验, 数学也不好, 高考数学刚及格. ...
- 2010-11-24 23:26
- 浏览 391
- 评论(0)