首页 > ACM题库 > HDU-杭电 > hdu 2670 Girl Love Value-动态规划-[解题报告]C++
2014
02-12

hdu 2670 Girl Love Value-动态规划-[解题报告]C++

Girl Love Value

问题描述 :

Love in college is a happy thing but always have so many pity boys or girls can not find it.
Now a chance is coming for lots of single boys. The Most beautiful and lovely and intelligent girl in HDU,named Kiki want to choose K single boys to travel Jolmo Lungma. You may ask one girls and K boys is not a interesting thing to K boys. But you may not know Kiki have a lot of friends which all are beautiful girl!!!!. Now you must be sure how wonderful things it is if you be choose by Kiki.

Problem is coming, n single boys want to go to travel with Kiki. But Kiki only choose K from them. Kiki every day will choose one single boy, so after K days the choosing will be end. Each boys have a Love value (Li) to Kiki, and also have a other value (Bi), if one boy can not be choose by Kiki his Love value will decrease Bi every day.
Kiki must choose K boys, so she want the total Love value maximum.

输入:

The input contains multiple test cases.
First line give the integer n,K (1<=K<=n<=1000)
Second line give n integer Li (Li <= 100000).
Last line give n integer Bi.(Bi<=1000)

输出:

The input contains multiple test cases.
First line give the integer n,K (1<=K<=n<=1000)
Second line give n integer Li (Li <= 100000).
Last line give n integer Bi.(Bi<=1000)

样例输入:

3 3
10 20 30
4 5 6
4 3
20 30 40 50
2 7 6 5

样例输出:

47
104

如果确定了选哪几个,顺序肯定是Li大的先选,所以可以按Li排序,再像0-1背包一样依次添加

 

 

 

 

 

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int dp[1001];
struct op
{
	int w,v;
}p[1001];
int cmp(const void *a,const void *b)
{
	struct op *c,*d;
	c=(struct op *)a;
	d=(struct op *)b;
	return d->v-c->v;
}
int main()
{
	int i,j,n,k,max;
	while(scanf("%d%d",&n,&k)!=-1)
	{
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
			scanf("%d",&p[i].w);
		for(i=0;i<n;i++)
			scanf("%d",&p[i].v);
		qsort(p,n,sizeof(p[0]),cmp);
		for(i=0;i<n;i++)
			for(j=k;j>=1;j--)
			{
				if(dp[j]<dp[j-1]+p[i].w-(j-1)*p[i].v)
				dp[j]=dp[j-1]+p[i].w-(j-1)*p[i].v;
			}
			printf("%d\n",dp[k]);
	}
	return 0;
}

 

解题转自:http://blog.csdn.net/aixiaoling1314/article/details/8952826


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }