题目是经典的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>
2using namespace std;
3
4int node[102][102];
5int len[102][102];
6int r, c;
7int 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}
35int 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 阅读(2471) |
评论 (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
posted @
2008-01-28 16:11 yoyouhappy 阅读(2199) |
评论 (1) |
编辑 收藏
有好长时间没有来这里了，一方面是因为校园网上CPPblog太慢了，一方面也是因为不想把这里变成灌水的地方，自己想说的都弄在了space上。。。
以后还是得坚持写这个学习笔记的，我还得加油，不能那么懒了，CTcoolL貌似都有点走火入魔了，我们俩都是怪人，somebody如是说^^
以后会多来这边的，我要努力学习，哈哈 还有 争取明天的励志奖学金~~~~!
God bless me && bless all~!
posted @
2007-10-21 12:03 yoyouhappy 阅读(259) |
评论 (1) |
编辑 收藏
摘要: WA了一次，最后发现竟然是多次计算时没给result赋初值，改了以后就AC了~
题目是写一个超简化版的贪吃蛇，在50*50的矩阵中，起始位置是蛇头位于的（25，30），蛇尾在（25，11），蛇占20个格。蛇可以向E W N S四个方向移动，当然不能反向移动，也不能撞倒自己或者撞倒墙.
阅读全文
posted @
2007-08-17 08:48 yoyouhappy 阅读(935) |
评论 (4) |
编辑 收藏
摘要: 注意:可以的话最好还是自己写qsort( )而不是调用stdlib.h里的qsort()函数，那样效率会高很多的
七种qsort排序方法
<本文中排序都是采用的从小到大排序>
阅读全文
posted @
2007-07-21 17:04 yoyouhappy 阅读(1227) |
评论 (4) |
编辑 收藏