Blog·Tanky WooABOUTRSS

HDU/HDOJ 1160 FatMouse's Speed

04 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:

http://acm.hdu.edu.cn/showproblem.php?pid=1160

简单的DP,但是纠结了2个小时,因为在输出最长子序列路径时搞晕了,把pre和id搞混了。。。

代码很乱,懒的整理了~~

#include 
#include 

using namespace std;

typedef struct Mouse{
    int weight;
    int speed;
    int id;
    int pre;
};

int cmp(const void *arg1, const void *arg2)
{
    Mouse *v1 = (Mouse*)arg1;
    Mouse *v2 = (Mouse*)arg2;
    if(v1->weight == v2->weight)
        return -(v1->speed - v2->speed);
    else
        return v1->weight - v2->weight;
}


Mouse mice[1005];
int dp[1005];
int que[1005];
int tt = 0;

int main()
{
    //freopen("input.txt", "r", stdin);
    int cnt = 0, p, q;
    while(cin >> p >> q)
    {
        mice[cnt].weight = p;
        mice[cnt].speed = q;
        mice[cnt].id = cnt;
        mice[cnt++].pre = -1;

    }
    qsort(mice, cnt, sizeof(Mouse), cmp);


    for(int i=0; imice[j].weight && mice[i].speed tmp)
        {
            tmp = dp[i];
            tmp_id = i;
        }
    cout << tmp << endl;
    tmp = mice[tmp_id].id;
    ////////////////////////
    /*
    cout << "weight" << " " << "speed" << " " << "id" << " " << "pre" << endl;
    for(int i=0; i=0; --i)
        cout << que[i] << endl;


}