CSU 1105

3020 ワード

acm

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1105
1105:打怪レベルアップSubmit Page
    Summary

Time Limit: 1セット

メモリLimit: 64 Mビット

Submitted: 357

Solved: 104
Description
多くのRPGゲームにとって、ストーリー以外はゲッターアップです。本題の任務は最短の時間ですべての戦いの勝利を勝ち取ることです。これらの戦闘は特定の順序で行われなければなりません。1ゲームごとに勝利すると、いくつかの補助薬を得て、力を高めることができます。この問題は2種類の補助薬しかありません。「1薬を加える」と「2薬を乗る」はそれぞれの力に1と2を加えます。
戦闘時間はあなたの力次第です。各戦闘は6つのパラメータで記述できます。p 1，p 2，t 1，t 2，w 1，w 2。もしあなたの力がp 1より小さいなら、あなたは戦いに負けます。あなたの力がp 2より大きいなら、t 2秒で戦闘を勝ちとします。力がp 1とp 2にある場合（p 1とp 2を含む）、戦闘時間はt 1からt 2まで直線的に減少する。例えばp 1=50、p 2=75、t 1=40、t 2=15、あなたの力は55で、戦闘に勝つには35秒かかります。戦闘時間は整数ではない可能性があります。最後の二つのパラメータw 1とw 2はそれぞれ戦闘に勝利した後に獲得した「1薬を加える」と「2薬を乗る」の数を表します。注意してください。すぐにこれらの補助薬を使う必要はありません。必要な時に使うことができますが、戦闘中に補助薬を使うことはできません。
各戦闘のパラメータを順番に与え、全ての戦闘に勝つために必要な最短総時間を出力します。戦闘は順序によって行われなければなりません。また、どの戦闘もスキップできません。
Input
最大25セットのテストデータを入力します。各グループのデータの第一の行為は二つの整数nとp(1<=n==1000,1<=p<=100)で、つまり戦闘の場数とあなたの初期の力の値です。以下のn行は、6個の整数p 1,p 2,t 1,t 2,w 1,w 2(1==p 1)である。
Output
各グループのデータに対して、最短総時間（単位：秒）を出力し、2桁の小数を保持します。解がなければ、「Impossible」を出力します。
Sample Input

1 55 
50 75 40 15 10 0
2 55
50 75 40 15 10 0
50 75 40 15 10 0
3 1
1 2 2 1 0 5
1 2 2 1 1 0
1 100 100 1 0 0
1 7
4 15 35 23 0 0
1 1
2 3 2 1 0 0
0 0

Sample Output

35.00
60.00
41.00
31.73
Impossible

ベント
Source湖南省第7回コンピュータプログラム設計コンテスト
考え：知っていることができます。+1があれば、そのまま食べてもいいです。*2は食べてもいいです。そして、力が100より大きいと無敵です。だから、多くの状態はないです。多くのブログを見たらdfsです。私はbfsを使っています。

#include
#include
#include
#include
using namespace std;
#define maxn 1005
int p1[maxn], p2[maxn], t1[maxn], t2[maxn], w1[maxn], w2[maxn];
int n,p;
struct node
{
    int now;
    int p;
    double ti;
    int h2;
    node() {}
    node(int a,int b,double c,int e)
    {
        now=a;
        p=b;
        ti=c;
        h2=e;
    }
};
struct CMP
{
    bool operator()(node a,node b)
    {
        return a.ti>b.ti;
    }
};
void bfs()
{
    priority_queue, CMP > q;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(node(1,p,0,0));
    int f=0;
    while(!q.empty())
    {
        node k=q.top();
        q.pop();
        if(k.now==n+1)
        {
            f=1;
            printf("%.2f
",k.ti);
            break;
        }
        int pos=k.now;
        if(k.pp2[pos])
        {
            c.ti=k.ti+t2[pos];
        }
        else
        {
            c.ti=k.ti+1.0*(1.0*p1[pos]*t2[pos]-1.0*p2[pos]*t1[pos]-(1.0*(t2[pos]-t1[pos])*k.p))/(1.0*p1[pos]-p2[pos]);
        }
        if(c.p<100)
        {
            q.push(c);
            int num=c.h2;
            for(int i=0; i

PHP APCプロファイル2セットとパラメータ詳細