hdu 1574

5647 ワード
RP問題
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 726    Accepted Submission(s): 216
Problem Description
人間社会の中で、いかなる個体も人柄を持っていて、人柄にはいろいろな形式があって、一つの形式から別の形式に転換することができて、一つの個体から別の個体に伝達して、転換と伝達の過程の中で、人柄は消えないで、創造することができなくて、これは、人柄の保存の法則です!
人品保存の法則はもっとイメージ的な説明で、良いことが起こったら、あなたはそこから利益を得て、必ずRPを一定量消費します.不幸なことが起こると、あなたはその中で損失をして、必ずRPを貯めます.
1つの期間内にN個のイベントが発生する可能性があると仮定し、各イベントはRP変化値a、RP敷居値b、および利得値cに対応する.RP変化値aが正で、利益値cは必ず負であり、現在のRP値がRP敷居値b以下である場合にのみ、このイベントが発生する可能性があり、このイベントが発生すると、RP値は|a|増加し、利益値は|c|減少する.逆に、RP変化値aが負であり、利益値cが必ず正であり、現在のRP値がRP敷居値b以上である場合にのみ、このイベントが発生する可能性があり、このイベントが発生すると、RP値が|a|減少し、利益値が|c|増加する.
1つのイベントが上記RP条件を満たす前提で発生するとは限らない.この時間までにRP値と利益値が0だったと仮定すると、この時間が過ぎた後、あなたが達成できる最大利益値はいくらですか?
注意:1人のRP値は負の場合があります.
 
Input
入力データの第1の挙動は、T組のテストデータがあることを示す正の整数Tである.各テストデータの最初の動作は、正の整数N(0 
Output
各入力セットに対応して、独立した行に正の整数を出力します.これは、最大の収益性値を示します.
 
Sample Input 

   
   
   
   

    
    
    
    3
1
-1 0 1
2
10 200 -1
-5 8 3
3
-5 0 4
10 -5 -5
-5 5 10

 
Sample Output 

   
   
   
   

    
    
    
    1
2
9

 
Author
lwg
 
Source
HDU 2007-1 Programming Contest
 
Recommend
linle
 
お久しぶりですね~~一递推~
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int dp[20005];
int vis[20005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int i,a,b,c;
        memset(vis,0,sizeof(vis));
        for(i=0;i<=20000;i++)
            dp[i]=-inf;
        dp[10000]=0;
        vis[10000]=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            b+=10000;
            int j;
            if(a<0)
            {
                for(j=b;j<=20000;j++)
                {
                    if(vis[j]==1)
                    {
                        if(vis[j+a])
                            dp[j+a]=max(dp[j]+c,dp[j+a]);
                        else
                        {
                            dp[j+a]=dp[j]+c;
                            vis[j+a]=1;
                        }
                    }
                }
            }
            else
            {
                //printf("asdf %d
",a+b);
                for(j=b;j>=0;j--)
                {
                    if(vis[j]==1)
                    {
                        if(vis[j+a]==1)
                            dp[j+a]=max(dp[j+a],dp[j]+c);
                        else
                        {
                            dp[j+a]=dp[j]+c;
                            vis[j+a]=1;
                        }
                        //printf("%d %d %d 
",c,j-a,dp[j]);
                    }
                }
            }
        }
        int mm=-inf;
        for(i=0;i<=20000;i++)
        {
            if(vis[i]==1&&mm<dp[i])
                mm=dp[i];
        }
        printf("%d
",mm);
    }
    return 0;
}

もう一つのコードはなぜ間違っているのか分かりません.教えてください.
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int dp[20005];
int vis[20005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int i,a,b,c;
        memset(vis,0,sizeof(vis));
        for(i=0;i<=20000;i++)
            dp[i]=-inf;
        dp[10000]=0;
        vis[10000]=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            b+=10000;
            int j;
            if(a<0)
            {
                for(j=a+b;j<=20000;j++)
                {
                    if(vis[j-a]==1)
                    {
                        if(vis[j])
                            dp[j]=max(dp[j-a]+c,dp[j]);
                        else
                        {
                            dp[j]=dp[j-a]+c;
                            vis[j]=1;
                        }

                    }
                }
            }
            else
            {
                //printf("asdf %d
",a+b);
                for(j=a+b;j>=a;j--)
                {
                    if(vis[j-a]==1)
                    {
                        if(vis[j])
                            dp[j]=max(dp[j-a]+c,dp[j]);
                        else
                        {
                            dp[j]=dp[j-a]+c;
                            vis[j]=1;
                        }
                        //printf("%d %d %d 
",c,j-a,dp[j]);
                    }
                }
            }
        }
        int mm=-inf;
        for(i=0;i<=20000;i++)
        {
            if(vis[i]==1&&mm<dp[i])
                mm=dp[i];
        }
        printf("%d
",mm);
    }
    return 0;
}
C#事前非同期ロードデータ
ACM刷題のHDU――今年の夏休みはAC