題目是經典的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 閱讀(2492) |
評論 (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 閱讀(2225) |
評論 (1) |
編輯 收藏
有好長時間沒有來這里了，一方面是因為校園網上CPPblog太慢了，一方面也是因為不想把這里變成灌水的地方，自己想說的都弄在了space上。。。
以后還是得堅持寫這個學習筆記的，我還得加油，不能那么懶了，CTcoolL貌似都有點走火入魔了，我們倆都是怪人，somebody如是說^^
以后會多來這邊的，我要努力學習，哈哈 還有 爭取明天的勵志獎學金~~~~!
God bless me && bless all~!
posted @
2007-10-21 12:03 yoyouhappy 閱讀(276) |
評論 (1) |
編輯 收藏
摘要: WA了一次，最后發現竟然是多次計算時沒給result賦初值，改了以后就AC了~
題目是寫一個超簡化版的貪吃蛇，在50*50的矩陣中，起始位置是蛇頭位于的（25，30），蛇尾在（25，11），蛇占20個格。蛇可以向E W N S四個方向移動，當然不能反向移動，也不能撞倒自己或者撞倒墻.
閱讀全文
posted @
2007-08-17 08:48 yoyouhappy 閱讀(956) |
評論 (4) |
編輯 收藏
摘要: 注意:可以的話最好還是自己寫qsort( )而不是調用stdlib.h里的qsort()函數，那樣效率會高很多的
七種qsort排序方法
<本文中排序都是采用的從小到大排序>
閱讀全文
posted @
2007-07-21 17:04 yoyouhappy 閱讀(1253) |
評論 (4) |
編輯 收藏