uva 11264 - Coin Collector(dp or 욕심)

2861 단어
Problem E Coin Collector Input: Standard Input
Output: Standard Output
 
Our dear Sultan is visiting a country where there are n different types of coin. He wants to collect as many different types of coin as you can. Now if he wants to withdraw X amount of money from a Bank, the Bank will give him this money using following algorithm.
 
withdraw(X){
if( X == 0) return;
Let Y be the highest valued coin that does not exceed X.
Give the customer Y valued coin.
withdraw(X-Y);
}
 
Now Sultan can withdraw any amount of money from the Bank. He should maximize the number of different coins that he can collect in a single withdrawal.
 
Input:
 
First line of the input contains T the number of test cases. Each of the test cases starts with n (1≤n≤1000), the number of different types of coin. Next line contains n integers C1, C2, ... , Cn the value of each coin type. C1 
Output:
 
For each test case output one line denoting the maximum number of coins that Sultan can collect in a single withdrawal. He can withdraw infinite amount of money from the Bank.
 
Sample Input
Sample Output
2 6 1 2 4 8 16 32 6 1 3 6 8 15 20  
6 4  
 
 
 
 
 
 
 
 
Problemsetter: Abdullah Al Mahmud
Special Thanks To: Mohammad Mahmudur Rahman
dp[i][j]는 전 i 중 j개를 선택한 가장 작은 합을 나타낸다.욕심을 부리거나
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <stack>
#include <set>
#include <cstring>
#include <stdlib.h>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1000+5;
const LL INF = 10000000000000;

int a[maxn];
LL dp[maxn][maxn];

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        for(int i = 0;i < n;i++){
            scanf("%d", &a[i]);
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < maxn;j++){
                dp[i][j] = INF;
            }
        }
        dp[0][0] = 0;
        dp[0][1] = 1;
        for(int i = 1;i < n;i++){
            for(int j = 0;j <= i+1;j++){
                dp[i][j] = dp[i-1][j];
                if(dp[i-1][j-1]+a[i] < a[i+1] || i == n-1)
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+a[i]);
            }
        }
        for(int i = n;i >= 0;i--){
            if(dp[n-1][i] != INF){
                printf("%d
", i);
                break;
            }
        }
    }
    return 0;
}
'유류 코드 개선 지침'독서 노트
[Unity] UI Elements의 UXML, USS에 지정된 고급 경로 이동

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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