zoj 3596 코스 선택 시스템 (dp, 01 가방)

제목 설명
n (≤ 500) 대수 (0 ≤ Hi () ≤ 10000, 0 ≤ Ci ≤ 100) 를 드 립 니 다. m 개 수 를 골 라 이 물건 을 최대 화하 라 고 합 니 다.
분석 하 다.
설정 x = ∑ mi = 0Hxi, y = ∑ mi = 0Cxi 는 원 등식 을 (x − y) 2 − 2 ∗ y2 로 바 꿀 수 있다. 분명히 우리 의 목 표 는 y 를 최대한 작 게 하 는 것 이다. 동시에 x 는 최대한 크 고 한 걸음 더 나 아가 고정된 y 를 정 하 는 것 이다. 우 리 는 x 를 최대한 크게 해 야 한다. 이것 이 바로 01 배낭 이 아닌가?
AC code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pb push_back
#define mp make_pair
#define PI acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MOD = 1e9+7;
const int MAX_P = 2e4+10;
const int maxn = 50000+10;
const int MAX_V = 5e5+10;
typedef long long LL;
typedef long double DB;
typedef pair<int,int> Pair;

LL dp[maxn];

Pair a[maxn];

int main() {
    int T;
    scanf("%d",&T );
    while (T--) {
        int n;
        scanf("%d",&n );
        int maxv = 0;
        for(int i=0 ; iscanf("%d%d",&a[i].fi,&a[i].se);
            maxv += a[i].se;
        }
        memset(dp,0,sizeof(dp));
        for(int i=0 ; ifor(int j = maxv ; j-a[i].se >=0 ;--j){
                dp[j] = max(dp[j],dp[j-a[i].se]+a[i].fi);
            }
        }
        LL ans=0;
        for(int i=0 ; i<=maxv ; ++i){
            ans = max(ans,dp[i]*dp[i]-(dp[i]+i)*i);
        }
        std::cout << ans << '
';
    }

    return 0;
}