codeforces 366C C. Dima and Salad(dp)

3965 단어 dpcodeforces

제목 링크:


codeforces 366C

제목 대의:


n개의 아이템을 주고 두 개의 속성이 있습니다. 마지막 첫 번째 속성의 총계가 두 번째 속성의 k배냐고 물었을 때 첫 번째 속성이 가장 크면 얼마입니까?

제목 분석:


4
  • 우리는 물품을 변형시켰다. 무게는 a[i]-b[i]*k이고 수익은 a이다. 그러면 우리는 무게를 플러스로 한 번 배낭을 만들고 품질을 마이너스로 절대치를 취하여 배낭을 한 번 만들고 무게가 같은 배낭의 수익의 합은 현재 무게의 최대 수익이다

  • AC 코드:

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #define MAX 107
    
    using namespace std;
    
    int dp[MAX*MAX],dd[MAX*MAX];
    
    int n,k,a[MAX],b[MAX],c[MAX];
    
    int main ( )
    {
        while ( ~scanf ( "%d%d" , &n , &k ) )
        {
            for ( int i = 0 ; i < n ; i++ )
                scanf ( "%d" , &a[i] );
            for ( int i = 0 ; i < n ; i++ )
                scanf ( "%d" , &b[i] );
            for ( int i = 0 ; i < n ; i++ )
                c[i] = a[i]-b[i]*k;
            memset ( dp , -0x3f , sizeof ( dp ) );
            memset ( dd , -0x3f , sizeof ( dd ) );
            dp[0] = dd[0] = 0;
            for ( int i = 0 ; i < n ; i++ )
                if ( c[i] >= 0 )
                    for ( int j = 10000 ; j >= c[i] ; j-- )
                        dp[j] = max ( dp[j-c[i]]+a[i] , dp[j] );
            for ( int i = 0 ; i < n ; i++ )
                if ( c[i] < 0 )
                {
                    c[i] = -c[i];
                    for ( int j = 10000 ; j >= c[i] ; j-- )
                        dd[j] = max ( dd[j-c[i]]+a[i] , dd[j] );
                }
            int ans = -1;
            for ( int i = 0; i <= 10000 ; i++ )
            {
                if ( dd[i] == 0 && dp[i] == 0 ) 
                    continue;
                ans = max ( ans , dp[i]+dd[i] );
            }
            printf ( "%d
    "
    , ans ); } }

    좋은 웹페이지 즐겨찾기