【神仙題】【CF 28 D】Don't fear,DravDeis kind

3690 ワード

トランスファゲート
Description
都市Zから都市3に向かってN台のトラックの車隊が走り、「恐怖のトンネル」というトンネルに来た.トラックの運転手の中には、怪物DravDeがそのトンネルで運転手を探しているという噂がある.一部の運転手は先に行くのが怖いが、他の人は後に行くのが怖い.しかし、一般的な状況を考えてみましょう.トラックごとに4つの数字で説明します.
•v、乗客や貨物を含むトラックの価値
•c、運転手本人を含む乗客数
•l、現在のトラックの前に入るべきトンネルの総数.そうすれば、現在の運転手は彼の恐怖を克服することができる(怪物がその車の前に現れたら、先に食べてしまう)
•r、現在のトラックの後に入るべきトンネルの総数.そうすれば、現在の運転手は彼の恐怖を克服することができる(怪物がその車の後ろに現れたら、先に食べてしまう)
路面が狭いので、DravDeが出てくると逃げられない.また、チームは再配置できません.トラックの順番は変えられませんが、トンネル付近に無期限にとどまるトラックがあります.あなたは、車隊の頭として、いくつかのトラックを移動すべきです(はい、これらのトラックの価値を無視します)、このように車隊の残りの部分はトンネルを通過することができます.いくつかのトラックを移動した後、残りのトラックの総価値は最大でいくらですか.
Input
1行目はトラック数(n)
次の(n)行、1行あたり4つの数、上記の順序でトラックの4つのパラメータを与えます
Output
2行出力します.1行目の出力は、価値が最大の場合の残りのトラック数を表します.
2行目は、選択されたトラック番号を出力します.任意に1種類出力すればよい
Hint
(0~leq~v~leq~10^4),(0~leq~)その他のパラメータ(leq~10^5)
Solution
よく考えた結果、同時に選択された2台の車に対して、総人数は(c+r+l)であるべきであることが分かった.そこで、同時に選択された車の上記パラメータは同じであるべきだと結論した.
そこで、上記の条件を満たしてこそ答えを更新することができ、1台の車に対して選択されたシーケンスの人数は固定されるべきだと教えてくれました.
明らかにこれは線形DPである.すると遷移方程式(f_i=max{f_j}+v_i)があり、(j)のパラメータと(i)と同じであるとともに、(j)が(i)の前にあるため(l_j+c_i=l_i)がある.この方程式に従って移行することができる.1つの(r=0)の位置に列挙するごとに、答えを更新できます.
Code

#include
#include
#include
#define rg register
#define ci const int
#define cl const long long

typedef long long int ll;

template 
inline void qr(T &x) {
    rg char ch=getchar(),lst=' ';
    while((ch > '9') || (ch < '0')) lst=ch,ch=getchar();
    while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(lst == '-') x=-x;
}

namespace IO {
    char buf[120];
}

template 
inline void qw(T x,const char aft,const bool pt) {
    if(x < 0) {x=-x,putchar('-');}
    rg int top=0;
    do {IO::buf[++top]=x%10+'0';} while(x/=10);
    while(top) putchar(IO::buf[top--]);
    if(pt) putchar(aft);
}

template 
inline T mmax(const T a,const T b) {return a > b ? a : b;}
template 
inline T mmin(const T a,const T b) {return a < b ? a : b;}
template 
inline T mabs(const T a) {return a < 0 ? -a : a;}

template 
inline void mswap(T &_a,T &_b) {
    T _temp=_a;_a=_b;_b=_temp;
}

const int maxn = 400010;

struct M {
    int v,c,l,r,sum,pos;
    inline bool operatorsum != _others.sum) return this->sum < _others.sum;
        return this->pos < _others.pos;
    }
};
M MU[maxn];

int n,ans;
int frog[maxn],pre[maxn],pcnt[maxn];
std::mapmp[maxn];

void dfs(ci);

int main() {
    qr(n);
    for(rg int i=1;i<=n;++i) {
        M &now=MU[i];
        qr(now.v);qr(now.c);qr(now.l);qr(now.r);
        now.sum=now.c+now.l+now.r;now.pos=i;
    }
    std::sort(MU+1,MU+1+n);
    for(rg int i=1;i<=n;++i) {
        int k;
        if(!MU[i].l) {
            frog[i]=MU[i].v;pcnt[i]=1;
        }
        else if((k=mp[MU[i].sum][MU[i].l]) != 0) {
            frog[i]=frog[k]+MU[i].v;pre[i]=k;pcnt[i]=pcnt[k]+1;
        }
        if(frog[i] && (frog[i] > frog[mp[MU[i].sum][MU[i].c+MU[i].l]])) mp[MU[i].sum][MU[i].l+MU[i].c]=i;
        if(!(MU[i].r) && (frog[ans] < frog[i])) ans=i;
    }
    qw(pcnt[ans],'
',true);
    dfs(ans);putchar('
');
    return 0;
}

void dfs(ci x) {
    if(!x) return;
    dfs(pre[x]);
    qw(MU[x].pos,' ',true);
}

Summary
DP遷移では,代数定式化により正しい遷移法を実証できた.
転載先:https://www.cnblogs.com/yifusuyi/p/9879795.html

図2点間の最短経路、すべての経路アルゴリズムC言語実現

hdu 1711 KMP