[CF 542F] Quest

作法：

這題我的作法是 greedy ，但DP也可以做，DP的作法可以參考官方詳解。
我們從花費時間少的問題看起，假設有個問題的花費時間為 $1$ ，那麼如果現在打算取他，這時候再拿一個花費時間為 $1$ 的放在這個問題的另一個分支會是最好的選擇，否則如果拿的問題是花費時間為 $t > 1$ 的問題，那麼這個時間 $1$ 的問題就失去優勢了，這時他就等價於一個花費時間為 $t$ 的問題了。並且我們知道當決定好要取時間 $1$ 的兩個問題時，一定是取價值最大的兩個，因此就得到了這樣的算法：按照花費時間由小到大看，如果當前這個花費時間 $t$ 有 $\geq 2$ 個問題，那就不斷把價值最大的兩個問題融合起來，變成一個花費時間為 $t+1$ 的問題，並且他的價值是兩個小問題的價值和。而如果只有一個問題，那就直接把他改成花費時間為 $t+1$ 的。這樣一直做下去直到所有東西都變成花費時間為 $T$ 的，取裡面的最大值就是答案了。比賽時我的理解方式其實是「把兩個問題融合起來變成一個新的問題」，因此是用 priority_queue 實作，後來想想其實把每個花費時間的問題都用一個 vector 裝起來去處理就可以了，那樣也蠻好寫的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
 
struct P
{
    int x,val ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? val<rhs.val : x>rhs.x ;
    }
};
 
priority_queue<P> pq ;
 
main()
{
    int n,T ; scanf("%d%d",&n,&T) ;
    for(int i=1;i<=n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        pq.push((P){x,y}) ;
    }
 
    int ans=0 ;
    while(pq.size()>1)
    {
        P p=pq.top() ; pq.pop() ;
        P q=pq.top() ; pq.pop() ;
        if(p.x!=q.x)
        {
            pq.push((P){q.x,p.val}) ;
            pq.push(q) ;
            continue ;
        }
        ans=max(ans,max(p.val,q.val)) ;
        if(p.x==T || q.x==T) break ;
        pq.push((P){p.x+1,p.val+q.val}) ;
    }
    while(!pq.empty()) ans=max(ans,pq.top().val) , pq.pop() ;
    printf("%d\n",ans) ;
}