程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 12260 Free Goodies

UVA - 12260 Free Goodies

編輯:C++入門知識

題意:覺得學長寫的很好,借鑒了:點擊打開鏈接

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct node{
    int x,y;
    bool operator <(const node &a)const {
        if (x != a.x)
            return x > a.x;
        return y < a.y;
    }
}arr[MAXN];
int n;
int f[MAXN][MAXN/2];
int cost[MAXN][MAXN/2];
char name[10];

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        scanf("%s",name);
        int sum = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d%d",&arr[i].x,&arr[i].y);
            sum += arr[i].x;
        }
        sort(arr+1,arr+1+n);
        memset(f,0,sizeof(f));
        memset(cost,0,sizeof(cost));
        int cur = 0;
        for (int i = (name[0]=='P'?2:1); i <= n; i++){
            ++cur;
            for (int j = 1; j <= (cur+1)/2; j++){
                int &ans = f[i][j] = f[i-1][j];
                cost[i][j] = cost[i-1][j];
                if (j == 1 || f[i-1][j-1]){
                    int tmp = f[i-1][j-1] + arr[i].y;
                    if (tmp > ans){
                        ans =tmp;
                        cost[i][j] = cost[i-1][j-1] + arr[i].x;
                    }
                    else if (tmp == ans)
                        cost[i][j] = min(cost[i][j],cost[i-1][j-1]+arr[i].x);
                } 
            }
        }
        printf("%d %d\n",sum-cost[n][(cur+1)/2],f[n][(cur+1)/2]);
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved