yoyouhappy的秘密花园
欢迎来到我的秘密花园^^
posts - 16,comments - 33,trackbacks - 0
题目是经典的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    iflen[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    forint i = 1; i <= r; ++i ){
47        forint 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 阅读(2301) | 评论 (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>
 4using namespace std;
 5
 6struct Device
 7{
 8    int nChoice;
 9    int quality[102][2];
10};
11
12int 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 阅读(2033) | 评论 (1)编辑 收藏
因为cpp blog访问速度太慢了,所以暂时搬到 yoyouhappy.blog.edu.cn
感觉还是cpp 这里比较好,等我换成网通再搬回来吧>_<
posted @ 2007-11-18 16:34 yoyouhappy 阅读(90) | 评论 (0)编辑 收藏
有好长时间没有来这里了,一方面是因为校园网上CPPblog太慢了,一方面也是因为不想把这里变成灌水的地方,自己想说的都弄在了space上。。。
以后还是得坚持写这个学习笔记的,我还得加油,不能那么懒了,CTcoolL貌似都有点走火入魔了,我们俩都是怪人,somebody如是说^^
以后会多来这边的,我要努力学习,哈哈 还有 争取明天的励志奖学金~~~~!
God bless me && bless all~! 
posted @ 2007-10-21 12:03 yoyouhappy 阅读(144) | 评论 (1)编辑 收藏
     摘要: JOJ DNA Sorting
PE后终于过了~  阅读全文
posted @ 2007-08-20 23:05 yoyouhappy 阅读(905) | 评论 (5)编辑 收藏
     摘要: 在做JOJ 1101 DNA sorting时发现了这个诡异的问题
9.04*100再%100=3?!  阅读全文
posted @ 2007-08-18 18:07 yoyouhappy 阅读(686) | 评论 (4)编辑 收藏
     摘要: WA了一次,最后发现竟然是多次计算时没给result赋初值,改了以后就AC了~

题目是写一个超简化版的贪吃蛇,在50*50的矩阵中,起始位置是蛇头位于的(25,30),蛇尾在(25,11),蛇占20个格。蛇可以向E W N S四个方向移动,当然不能反向移动,也不能撞倒自己或者撞倒墙.
  阅读全文
posted @ 2007-08-17 08:48 yoyouhappy 阅读(804) | 评论 (4)编辑 收藏
     摘要: POJ 1002题 只是换了一句就AC了,诡异~~~  阅读全文
posted @ 2007-08-06 20:50 yoyouhappy 阅读(2973) | 评论 (6)编辑 收藏
     摘要: 注意:可以的话最好还是自己写qsort( )而不是调用stdlib.h里的qsort()函数,那样效率会高很多的

七种qsort排序方法
<本文中排序都是采用的从小到大排序>

  阅读全文
posted @ 2007-07-21 17:04 yoyouhappy 阅读(1033) | 评论 (4)编辑 收藏
     摘要: 刚刚想查一下cout的精度,却看到了这篇文章,keke我是学到重载运算符才大概明白cout是怎么回事的~这篇文章很易懂,对初学者会有帮助奥^_^
  阅读全文
posted @ 2007-07-20 19:52 yoyouhappy 阅读(275) | 评论 (0)编辑 收藏
仅列出标题  下一页
Priceline Travel
Priceline Travel