HDU 2184 - Cow Exhibition(백팩)

3492 단어 DP
Cow Exhibition
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 9217
 
Accepted: 3507
Description
"Fat and docile, big and dumb, they look so stupid, they aren't much
fun..."
- Cows with Guns by Dana Lyons
The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.
Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.
Input
* Line 1: A single integer N, the number of cows
* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.
Output
* Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.
Sample Input 
5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample Output 
8

                                                                   
제목:
n조(1<=n<=100) 데이터를 주고 s값(-100<=s<=1000)과 f값(-100<=f<=1000)이 있는 몇 조를 선택하여 s와 f가 0보다 작지 않고 총계가 가장 크다.
아이디어:
제목은 가방 문제로 전환할 수 있다. s값을 무게로 하고 f값을 가치로 한다. s값이 마이너스일 수 있기 때문에 숫자를 100000으로 앞당기고 dp[100000]를 원점으로 한다.
주의해야 할 것은 s[i]가 0보다 크면 역추하고 s[i]가 0보다 작으면 정추한다.dp[j] = max (dp[j], dp[i-s[i]]+f[i]);
code: 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int inf=0xfffffff;
typedef long long ll;
using namespace std;

int s[105], f[105];
int dp[200005];
int main()
{
    //freopen("in", "r", stdin);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++){
        scanf("%d %d", &s[i], &f[i]);
    }
    fill(dp, dp+200005, -inf);
    dp[100000] = 0;
    for(int i = 0; i < n; i ++){
        if(s[i] > 0){
            for(int j = 200000; j >= s[i]; j --){
                if(dp[j - s[i]] > -inf){
                    dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
                }
            }
        }
       else{
            for(int j = 0; j <= 200000 + s[i]; j++){
                if(dp[j - s[i]] > -inf){
                    dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 100000; i <= 200000; i++){
        if(dp[i] >= 0 && dp[i] + i - 100000 > ans)
            ans = dp[i] + i - 100000;
    }
    printf("%d
", ans);
    return 0;
}
Dropbox API를 사용하여 Appwrite 파일 백업 함수 만들기
S3 콘텐츠에 대한 기본 인증 + HTTPS 게시

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage