題目是經(jīng)典的DP入門(mén)，原來(lái)CTcoolL有一次拿來(lái)要做，當(dāng)時(shí)還不知DP為何物，想要暴搜，現(xiàn)在又重新翻出來(lái)做一下
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 閱讀(2500) |
評(píng)論 (5) |
編輯 收藏題目大意：
產(chǎn)品有n個(gè)部分 組成 每個(gè)部分有m種選擇，每個(gè)部件 有bandwith和price兩種屬性
求 一種選擇方案使B/P 最大 其中 B是各個(gè)部件bandwith的最小值 P是各個(gè)部件price的和
我的做法：
將bandwith排序，然后分別以每一個(gè)bandwith最為最小值時(shí) 求出可取方案中price值最小的 那個(gè)（即 使B/P最大）
然后綜合起來(lái) 求最大的B/P
下面是我的代碼：
雖然AC了，但是還是有一點(diǎn)疑惑，在某一minBand為最小值時(shí)，所取得方案中肯定包含一個(gè)產(chǎn)品選擇的bandwith = minBand，否則最小值不是minBand，但是我沒(méi)有做這個(gè)判斷
代碼如下，僅作參考：
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++){//選每一種產(chǎn)品
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 閱讀(2233) |
評(píng)論 (1) |
編輯 收藏
有好長(zhǎng)時(shí)間沒(méi)有來(lái)這里了，一方面是因?yàn)樾@網(wǎng)上CPPblog太慢了，一方面也是因?yàn)椴幌氚堰@里變成灌水的地方，自己想說(shuō)的都弄在了space上。。。
以后還是得堅(jiān)持寫(xiě)這個(gè)學(xué)習(xí)筆記的，我還得加油，不能那么懶了，CTcoolL貌似都有點(diǎn)走火入魔了，我們倆都是怪人，somebody如是說(shuō)^^
以后會(huì)多來(lái)這邊的，我要努力學(xué)習(xí)，哈哈 還有 爭(zhēng)取明天的勵(lì)志獎(jiǎng)學(xué)金~~~~!
God bless me && bless all~!
posted @
2007-10-21 12:03 yoyouhappy 閱讀(280) |
評(píng)論 (1) |
編輯 收藏
摘要: WA了一次，最后發(fā)現(xiàn)竟然是多次計(jì)算時(shí)沒(méi)給result賦初值，改了以后就AC了~
題目是寫(xiě)一個(gè)超簡(jiǎn)化版的貪吃蛇，在50*50的矩陣中，起始位置是蛇頭位于的（25，30），蛇尾在（25，11），蛇占20個(gè)格。蛇可以向E W N S四個(gè)方向移動(dòng)，當(dāng)然不能反向移動(dòng)，也不能撞倒自己或者撞倒墻.
閱讀全文
posted @
2007-08-17 08:48 yoyouhappy 閱讀(963) |
評(píng)論 (4) |
編輯 收藏
摘要: 注意:可以的話最好還是自己寫(xiě)qsort( )而不是調(diào)用stdlib.h里的qsort()函數(shù)，那樣效率會(huì)高很多的
七種qsort排序方法
<本文中排序都是采用的從小到大排序>
閱讀全文
posted @
2007-07-21 17:04 yoyouhappy 閱讀(1268) |
評(píng)論 (4) |
編輯 收藏