POJ 2184 Cow Exhibition(부피가 음수일 경우 01 가방의 처리 + 문제 전환)

제목: 소가 많아요. 소마다 지능과 유머가 있어요. 소를 골라야 해요. 지능과 유머의 총계가 가장 커요. 그 중에서 지능의 총계와 유머의 총계는 마이너스가 될 수 없어요.
mark: 변종의 01가방은 지능을 부피로 볼 수 있고 유머를 가치로 볼 수 있다. 그러면 부피와 가치가 모두 정가의 최대치인 01가방으로 바뀐다.
마이너스가 있기 때문에 부피당 +1000을 기록한 다음에 그 부피로 최대치를 얻었을 때 1000을 얼마나 썼는지 수조를 만들어 기록할 수 있다.
dp방정식:ans=max(dp[j]+j-cnt[j]*1000)
dp[j]는 부피가 j일 때 얻는 가장 큰 가치를 나타낸다. 즉, 지능이 j일 때 가장 큰 유머를 만든다.
전환 조건: dp[j]-cnt[j]*1000
먼저 데이터 범위를 계산합니다.
모두 100조수로 -1000에서 1000까지 부피의 범위는 -100*1000에서 100*1000까지입니다.
평이 이동 후 우리가 처리해야 할 데이터 범위는 0에서 200000이고 새로운 원점은 100000이 된다.

#include
#include
#include
#define INF 0xffffff
#define N 1000
#define MAX 200010
using namespace std;

int dp[MAX],cnt[MAX];
int v[110],w[110],sum;

int main()
{
    int n,ans;
    while(scanf("%d",&n)!=EOF)
    {
        sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&v[i],&w[i]);
            if(v[i]<0 && w[i]<0)   // v[i] w[i]      
            {
                i--;
                n--;
                continue;
            }
            v[i]+=1000;   //     1000,        
            sum+=v[i];    //     01      
        }
        for(int i=1;i<=sum;i++)   //                 
            dp[i]=-INF;            //           01     
        dp[0]=0;
        memset(cnt,0,sizeof(cnt));    //cnt                 1000.
        for(int i=1;i<=n;i++)
        {
            for(int j=sum;j>=v[i];j--)
            {
                if(dp[j]-cnt[j]*N=0 && i-cnt[i]*N>=0)
                ans=max(ans,dp[i]+i-cnt[i]*N);
        }
        printf("%d
",ans);
    }
    return 0;
}

또 하나의 해법이 있다.
부피가 마이너스 v-c[i]>v이면 작은 것부터 큰 것까지 누적됩니다.

#include
#include
#include
#define INF 0xffffff
#define M 200000
#define MAX 200010
#define N 110

using namespace std;

int dp[MAX],w[N],v[N],ans;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d",&v[i],&w[i]);
        for(int i=1;i<=M;i++)
            dp[i]=-INF;
        dp[100000]=0;
        for(int i=1;i<=n;i++)
        {
            if(v[i]<0)
            {
                for(int j=0;j-v[i]<=M;j++)
                {
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
            else
            {
                for(int j=M;j>=v[i];j--)
                {
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        ans=0;
        for(int i=100000;i<=M;i++)
        {
            if(dp[i]>0)
                ans=max(dp[i]+i-100000,ans);
        }
        printf("%d
",ans);
    }
    return 0;
}

ans는 -1로 초기화할 수 없습니다.
= =!