【HDU 6495】氷水チャレンジ(dp)

タイトルリンク
氷水チャレンジTime Limit:2000/1000 MS(Java/others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 377    Accepted Submission(s): 139   Problem Description Polar Bear Pitching helps you crystallize your message.The stage could not be any cooler,and we mean literally:a hole cut through the ice in the frozen Baltic Sea.2050は挑戦的なイベントであるPolar Bear Pitchingがある.体験人は氷の中に飛び込んで自分の恐怖、変化、夢を語る.これは時間制限のないスピーチで、氷水の中でどのくらい滞在できるかを見てみましょう.今、私たちは順番にnつの氷水の挑戦に直面して、すべての挑戦はあなたが受け入れるか受け入れないかを選択することができます.i番目の挑戦を受けるとai点の体力を失うことになります.挑戦する環境が異なるため、挑戦する前に体力xがmin(x,bi)になります.この挑戦を完了すると、体力はx-aiになります.体力はどんな場合でも0以下ではいけません.i番目の挑戦を受け入れるかどうかにかかわらず、この挑戦が終わったら、あなたの体力はciを増やします.今、私たちは最大どれだけの挑戦を完成できるか知りたいです.    Input 1行目の正の整数T (T≦50)はデータ群数を表す.次のT組のデータ、各組の第1行の2つの正の整数n、c (1≦n≦103,1≦c≦109)は,挑戦の数と初期体力を表し,次いでn行,各行の3つの非負の整数ai,bi,ci(0≦ai,bi,ci≦109)である.    Outputは、データのセットごとに1行1つの数を出力し、最大いくつかの課題を達成できることを示します.    Sample Input

2 3 10 1 2 0 4 8 3 6 10 1 2 1 1 1 1 1 1 1     Sample Output

2 0
 
【問題解きの考え方】
dp[i][j]を、前のi個のチャレンジがj個のチャレンジに当選したときの余剰体力の最大値とする.それは簡単です.
i番目の挑戦を受け入れなければ:dp[i][j]=max(dp[i][j],dp[i-1][j]+c[i])
i番目の挑戦を受ければ:dp[i][j]=max(dp[i][j],min(dp[i-1][j-1],b[i])-a[i]+c[i])
ここで注意が必要なときに問題を書くときはdp[i][0]も更新する必要があることを忘れないでください!!またlong longと書くのを覚えていますよ!
【コード】

#include
using namespace std;
typedef long long LL;
const int maxn=1005;
const LL INF=0x3f3f3f3f;
LL dp[maxn][maxn],a[maxn],b[maxn],c[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,-INF,sizeof(dp));
        dp[0][0]=m;
        for(int i=1;i<=n;i++)
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=dp[i-1][0]+c[i];
            for(int j=1;j<=i;j++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j]+c[i]);
                if(min(dp[i-1][j-1],b[i])>a[i])
                    dp[i][j]=max(dp[i][j],min(dp[i-1][j-1],b[i])-a[i]+c[i]);
            }
        }
        for(int i=n;i>=0;i--)
        {
            if(dp[n][i]>0)
            {
                printf("%d
",i);
                break;
            }
        }
    }

}