程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> WUST OJ 1421 we love girl(貪心或DP）

WUST OJ 1421 we love girl(貪心或DP）

編輯：關於C++

Description
When taking part in ACM Programming Contest,many school hope girls for reception like ccnu,cug and so on.So this year our wust send more girls as possible to have a reception.The ratio of male to female of wust is seven to one,so we may not have so many girls.Of course the rest receptionist is boys.

Now there are n schools take part in Wust ACM Programming Contest,x girls and y boys is willing to help.If a school is received buy girls,they will get p satisfaction.If received buy boys ,they will get q satisfaction.We want to improve the total satisfaction of every school.Do you know the max satisfaction?

Input
The first line contains an integer T(T<=100), indicates the number of cases.For each test case,the first line contains three positive integers n (1<=n<=20),x and y (x>=0,y>=0,x+y>=n).n is the amount of schools and x is the amount of girls and y is the amount of boys.Then n lines follows, each line contains two integers pi and qi which means the two satisfaction of girls and boys.

Output
For each test case,print one integer which is the max satisfaction.

Sample Input
2
3 2 1
2 1
4 2
1 2
4 2 2
3 2
2 4
10 9
4 0

Sample Output
8

這個題當時貪心寫的。n比較小，發揮不了貪心優勢。

由於只有兩種選擇，選擇一種就意味著放棄另一種。

我們貪心的策略就是按照選男孩和女孩差值排序，然後每次

選最優的（如果可能）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int INF = 0x3f3f3f3f;
const int maxn=(1e5+100)*2;
struct node{
    int x,y;
    int val;
}e[25];
int t,n,x,y;
int cmp(node l1,node l2)
{
    return l1.val>l2.val;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&y);
        int sum=0,ans=0;
        REPF(i,1,n)
        {
            scanf("%d%d",&e[i].x,&e[i].y);
            e[i].val=abs(e[i].x-e[i].y);
        }
        sort(e+1,e+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(e[i].x>e[i].y&&x)
            {
                ans+=e[i].x;
                x--;
            }
            else if(e[i].x

顯然也可以DP做。設前i個人選了j個女孩的最大值。 
注意如果x>n要令x=n..
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int INF = 0x3f3f3f3f;
int t,n,x,y;
int c1[110],c2[110];
int dp[110][110];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&y);
        REPF(i,1,n)
          scanf("%d%d",&c1[i],&c2[i]);
        if(x>n) x=n;
        for(int i=0;i<=n;i++)
           for(int j=0;j<=x;j++) dp[i][j]=-INF;
        for(int i=1;i<=x;i++)
            dp[i][i]=dp[i-1][i-1]+c1[i];
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=x;j++)
            {
                if(i-j>y) continue;
                dp[i][j]=dp[i-1][j]+c2[i];
                if(j>0) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+c1[i]);
            }
        }
        int ans=-INF;
        for(int i=0;i<=x;i++)
            ans=max(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return  0;
}


/*

*/