2681_1.cpp

HDOJ2501-2681acm解题报告

//3.17 3 H wa  自信心严重受挫....
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef struct{int ss,tt;}st;
st t[220];
bool cmp(st a,st b)
{
	return a.ss<=b.ss;//按照智商升序排列
}
int n,k,maxk,maxp,dp[205][205][505];
/*void dfs(int u,int p)
{
	if(u>k)
	{
		if(p>maxp)
			maxp=p;
		return ;
	}
	dfs(u+1,p);
	if(abs(t[u].ss-maxx)<=maxk && abs(t[u].ss-minn)<=maxk && t[u].tt+p>maxp)
	{
		if(t[u].ss>maxx)
			maxx = t[u].ss;
		if(t[u].ss<minn)
			minn = t[u].ss;
		dfs(u+1,t[u].tt+p);
	}
}*/

/*void pack()
{
	int i,j;
	for(i=0;i<n;i++)
		m[n][i]=0;
	m[n][]
}*/
int maxf(int a,int b)
{return a>b?a:b;}

/*](0<=i<N, i<=j<N, 1<=k<=K)表示把第i个
的intelligence_value作为最小值min,前j个中
取k个的最大prettiness_value值*/
/*int dp(int i,int j,int k)
{
	
		//for(j=0;j<i;j++)
		//{
			if(t[j].ss-t[i].ss>maxk)
				return 0;
		//}
	//	return maxf(dp(i,j - 1, k),dp(i, j – 1, k - 1) + t[j].tt); 
			//if(maxf(dp(i,j-1,k),dp(i,j-1,k-1)+t[j].tt)> maxp)
				return maxf(dp(i,j-1,k),dp(i,j-1, k-1) +t[j].tt);

}*/
int main()
{
	freopen("C:\\Documents and Settings\\Administrator\\桌面\\test.txt","r",stdin);

	int m,i,j,r,s,temp;
	while(scanf("%d%d%d",&n,&k,&maxk)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&t[i].ss,&t[i].tt);
		maxp=0;
		sort(t,t+n,cmp);
		//dfs(0,0,t[0].ss,t[0].ss);
		//printf("%d\n",dp(0,0,0));
		memset(dp,0,sizeof(dp));
		/*](0<=i<N, i<=j<N, 1<=k<=K)表示把第i个
的intelligence_value作为最小值min,前j个中
取k个的最大prettiness_value值*/
		for(i=0;i<n;i++)
		{
			//if(dp[i][j][0]<t[j].tt)
					dp[i][0][0]=t[i].tt;
			for(j=i;j<n;j++)
			{
				dp[i][j][0]=dp[i][j-1][0];
			if(t[j].ss - t[i].ss>maxk)
					break;
				for(r=0;r<k;r++)
				{
					dp[i][j][k]=
						maxf(dp[i][j-1][k],dp[i][j-1][k-1]+t[j].tt);
				}
			}
		} 
		printf("%d\n",dp[n-1][n-1][k-1]);
	}
}