|
|
#include <iostream>
using namespace std;
int node[102][102];
int len[102][102];
int r, c;
int getLength( int i, int j )
{
if( len[i][j] > 0 )
return len[i][j];
int max = 0;
if( i + 1 <= r && node[i][j] > node[i+1][j] ){
int x = getLength( i + 1, j ) + 1;
if( max < x )
max = x;
}
if( j + 1 <= c && node[i][j] > node[i][j+1] ){
int x = getLength( i, j + 1 ) + 1;
if( max < x )
max = x;
}
if( i - 1 > 0 && node[i][j] > node[i-1][j] ){
int x = getLength( i - 1, j ) + 1;
if( max < x )
max = x;
}
if( j - 1 > 0 && node[i][j] > node[i][j-1] ){
int x = getLength( i, j - 1 ) + 1;
if( max < x)
max = x;
}
return max;
}
int main()
{
cin >> r >> c;
for ( int i = 1; i <= r; ++i ){
for ( int j = 1; j <= c; ++j ){
cin >> node[i][j];
len[i][j] = 0;
}
}
int maxLen = 0;
for( int i = 1; i <= r; ++i ){
for( int j = 1; j <= c; ++j ){
len[i][j] = getLength( i, j );
if( maxLen < len[i][j] )
maxLen = len[i][j];
}
}
cout << maxLen + 1<<endl;
system( "pause" );
}
題目大意:
產(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è)判斷
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
struct Device
{
int nChoice;
int quality[102][2];
};
int main()
{
int ncase;
cin >> ncase;
while ( ncase-- ){
int n;
double ratio = 0;
set <int> intSet;
set <int>::iterator sp;
cin >> n;
Device *s = new Device[n];
for( int i = 0; i < n; i++ ) {
cin >> s[i].nChoice;
for( int j = 0; j < s[i].nChoice; j++ ){
cin >> s[i].quality[j][0] >> s[i].quality[j][1];
intSet.insert( s[i].quality[j][0] );
}
}
for( sp = intSet.begin(); sp != intSet.end(); sp++ ){
int totalPrice = 0;
int minBand = *sp;
for( int i = 0; i < n; i++){//選每一種產(chǎn)品
int min = 100000;
for( int j = 0; j < s[i].nChoice; j++ ){
if( s[i].quality[j][0] >= minBand && min > s[i].quality[j][1] )
min = s[i].quality[j][1];
}
totalPrice += min;
}
if( ratio < (double) (minBand) / (double) totalPrice ){
ratio = (double) (minBand) / (double) totalPrice;
}
}
printf( "%.3lf\n", ratio );
delete s;
}
system("pause");
return 0;
}