题目是经典的DP入门,原来CTcoolL有一次拿来要做,当时还不知DP为何物,想要暴搜,现在又重新翻出来做一下
DP方程:len[ i ][ j ] = max{ len[ i-1][ j ], len[ i ][ j-1], len[ i+1][ j ], len[ i ][ j+1] };
代码如下:
1
#include <iostream>
2
using namespace std;
3
4
int node[102][102];
5
int len[102][102];
6
int r, c;
7
int getLength( int i, int j )
8
{
9
if( len[i][j] > 0 )
10
return len[i][j];
11
int max = 0;
12
if( i + 1 <= r && node[i][j] > node[i+1][j] ){
13
int x = getLength( i + 1, j ) + 1;
14
if( max < x )
15
max = x;
16
}
17
if( j + 1 <= c && node[i][j] > node[i][j+1] ){
18
int x = getLength( i, j + 1 ) + 1;
19
if( max < x )
20
max = x;
21
}
22
if( i - 1 > 0 && node[i][j] > node[i-1][j] ){
23
int x = getLength( i - 1, j ) + 1;
24
if( max < x )
25
max = x;
26
}
27
if( j - 1 > 0 && node[i][j] > node[i][j-1] ){
28
int x = getLength( i, j - 1 ) + 1;
29
if( max < x)
30
max = x;
31
}
32
return max;
33
34
}
35
int main()
36
{
37
38
cin >> r >> c;
39
for ( int i = 1; i <= r; ++i ){
40
for ( int j = 1; j <= c; ++j ){
41
cin >> node[i][j];
42
len[i][j] = 0;
43
}
44
}
45
int maxLen = 0;
46
for( int i = 1; i <= r; ++i ){
47
for( int j = 1; j <= c; ++j ){
48
len[i][j] = getLength( i, j );
49
if( maxLen < len[i][j] )
50
maxLen = len[i][j];
51
}
52
}
53
cout << maxLen + 1<<endl;
54
system( "pause" );
55
}
56
posted @
2008-01-28 16:19 yoyouhappy 阅读(2475) |
评论 (5) |
编辑 收藏
题目大意:
产品有n个部分 组成 每个部分有m种选择,每个部件 有bandwith和price两种属性
求 一种选择方案使B/P 最大 其中 B是各个部件bandwith的最小值 P是各个部件price的和
我的做法:
将bandwith排序,然后分别以每一个bandwith最为最小值时 求出可取方案中price值最小的 那个(即 使B/P最大)
然后综合起来 求最大的B/P
下面是我的代码:
虽然AC了,但是还是有一点疑惑,在某一minBand为最小值时,所取得方案中肯定包含一个产品选择的bandwith = minBand,否则最小值不是minBand,但是我没有做这个判断
代码如下,仅作参考:
1

#include <iostream>
2

#include <set>
3

#include <algorithm>
4

using namespace std;
5

6

struct Device
7

{
8

int nChoice;
9

int quality[102][2];
10

};
11

12

int main()
13

{
14

int ncase;
15

cin >> ncase;
16

while ( ncase-- ){
17

18

int n;
19

double ratio = 0;
20

set <int> intSet;
21

set <int>::iterator sp;
22

cin >> n;
23

Device *s = new Device[n];
24
25

for( int i = 0; i < n; i++ ) {
26

cin >> s[i].nChoice;
27

for( int j = 0; j < s[i].nChoice; j++ ){
28

cin >> s[i].quality[j][0] >> s[i].quality[j][1];
29

intSet.insert( s[i].quality[j][0] );
30

}
31

}
32
33

for( sp = intSet.begin(); sp != intSet.end(); sp++ ){
34

int totalPrice = 0;
35

int minBand = *sp;
36

for( int i = 0; i < n; i++){//选每一种产品
37
int min = 100000;38

for( int j = 0; j < s[i].nChoice; j++ ){
39

if( s[i].quality[j][0] >= minBand && min > s[i].quality[j][1] )
40

min = s[i].quality[j][1];
41

}
42

totalPrice += min;
43

}
44

if( ratio < (double) (minBand) / (double) totalPrice ){
45

ratio = (double) (minBand) / (double) totalPrice;
46

}
47

}
48

printf( "%.3lf\n", ratio );
49

50

delete s;
51

}
52

system("pause");
53

return 0;
54

}
55

一开始,我写的是min = s[i].quality[0][1];弄了好久都不知道哪里错了,后来发现原来第一个不一定取,这个做每次都toalPrice都是一样的....标出来,警示自己一下,呵呵 估计 大家都没有错的这么白痴的 >_<
posted @
2008-01-28 16:11 yoyouhappy 阅读(2202) |
评论 (1) |
编辑 收藏
有好长时间没有来这里了,一方面是因为校园网上CPPblog太慢了,一方面也是因为不想把这里变成灌水的地方,自己想说的都弄在了space上。。。
以后还是得坚持写这个学习笔记的,我还得加油,不能那么懒了,CTcoolL貌似都有点走火入魔了,我们俩都是怪人,somebody如是说^^
以后会多来这边的,我要努力学习,哈哈 还有 争取明天的励志奖学金~~~~!
God bless me && bless all~!
posted @
2007-10-21 12:03 yoyouhappy 阅读(261) |
评论 (1) |
编辑 收藏
摘要: WA了一次,最后发现竟然是多次计算时没给result赋初值,改了以后就AC了~
题目是写一个超简化版的贪吃蛇,在50*50的矩阵中,起始位置是蛇头位于的(25,30),蛇尾在(25,11),蛇占20个格。蛇可以向E W N S四个方向移动,当然不能反向移动,也不能撞倒自己或者撞倒墙.
阅读全文
posted @
2007-08-17 08:48 yoyouhappy 阅读(937) |
评论 (4) |
编辑 收藏
摘要: 注意:可以的话最好还是自己写qsort( )而不是调用stdlib.h里的qsort()函数,那样效率会高很多的
七种qsort排序方法
<本文中排序都是采用的从小到大排序>
阅读全文
posted @
2007-07-21 17:04 yoyouhappy 阅读(1229) |
评论 (4) |
编辑 收藏