UVA DP 入门专题

674-Coin Change

17132

47.12%

5842

89.90%

10073734

674

Coin Change

Accepted

C++

2.076

2012-05-04 11:09:02

状态转移方程：dp[j] = dp[j]+dp[j-cost[i]];

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 7500
using namespace std;

int cost[6]={0,1,5,10,25,50};
int dp[MAXN];

int main()
{
  //freopen("input.txt","r",stdin);
    int n,i,j;
    while(scanf("%d",&n)!=EOF){
        for(i=0; i<=n; ++i)
            dp[i]=1;
        for(i=2; i<=5; ++i){
            for(j=cost[i]; j<=n; ++j)
                dp[j]=dp[j]+dp[j-cost[i]];
        } 
        printf("%d\n",dp[n]);
    }
    return 0;
}

10131-Is Bigger Smarter?

16114

37.77%

4752

84.85%

10074426

10131

Is Bigger Smarter?

Accepted

C++

0.016

2012-05-04 14:45:20

先按重量大小排序，然后求IQ的最长递减子序列

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;


class point{
public:
	int weight;
	int iq;
	int number;
}elephant[1005];

bool cmp(const point& a,const point& b){
	if(a.weight==b.weight)
		return a.iq<b.iq;
	return a.weight<b.weight;
}

class Ans{
public:
	int num;
	int pre;
}ans[1005];

int main()
{
  	//freopen("input.txt","r",stdin);
	int index=0,i,j;
	while(scanf("%d %d",&elephant[index].weight,&elephant[index].iq)!=EOF)
		elephant[index].number=index+1, ++index;

	sort(elephant,elephant+index,cmp);

	for(i=0; i<index; ++i){
		ans[i].num=1, ans[i].pre=i;
	}

	for(i=1; i<index; ++i){
		int maxNum=0,pre;
		for(j=0; j<i; ++j){
			if(elephant[j].weight<elephant[i].weight && elephant[j].iq>elephant[i].iq && ans[j].num+1>maxNum)
				maxNum=ans[j].num+1, pre=j;
		}
		if(maxNum>ans[i].num){
			ans[i].num = maxNum;
			ans[i].pre = pre;
		}
	}

	int maxPos=0, maxNum=1;
	for(i=1; i<index; ++i){
		if(ans[i].num>maxNum)
			maxNum=ans[i].num, maxPos=i;
	}
	printf("%d\n",maxNum);
	

	stack<int>st;
	while(maxNum--){
		st.push(elephant[maxPos].number);
		maxPos = ans[maxPos].pre;
	}
	while(!st.empty()){
		printf("%d\n",st.top());
		st.pop();
	}
	return 0;
}

562-Dividing coins

16643

30.22%

3921

81.23%

10074473

562

Dividing coins

Accepted

C++

0.040

2012-05-04 15:03:51

01背包问题。

#include<cstdio>
#include<cstring>

int value[105],dp[25000];
int max(int a,int b){ return a>b?a:b; }

int main()
{
	//freopen("input.txt","r",stdin);
	int cas, m, i, j;
	
	scanf("%d",&cas);
	
	while(cas--){
		scanf("%d",&m);
		
		int sum=0;
		for(i=0; i<m; ++i){
			scanf("%d",&value[i]);
			sum += value[i];
		}
	
		memset(dp,0,sizeof(dp));
		for(i=0; i<m; ++i){
			for(j=sum/2; j>=value[i]; --j)
				dp[j] = max(dp[j-value[i]]+value[i],dp[j]);
		}
		printf("%d\n",sum-dp[sum/2]*2);
	}
	return 0;
}

10066-The Twin Towers

11414

44.45%

4465

86.58%

10074525

10066

The Twin Towers

Accepted

C++

0.012

2012-05-04 15:26:08

最长公共子序列

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int max(int a,int b){return a>b?a:b;}
int dp[105][105];
int tow1[105],tow2[105];

int main()
{
//	freopen("input.txt","r",stdin);
	int cas=1;
	int N1,N2,i,j;
	while(scanf("%d %d",&N1,&N2)!=EOF){
		if(!N1&&!N2) break;
		
		// input
		for(i=1; i<=N1; ++i)
			scanf("%d",&tow1[i]);
		for(i=1; i<=N2; ++i)
			scanf("%d",&tow2[i]);

		printf("Twin Towers #%d\n",cas++);
		memset(dp,0,sizeof(dp));
	
		for(i=1; i<=N1; ++i){
			for(j=1; j<=N2; ++j){
				if(tow1[i]==tow2[j]) dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
		printf("Number of Tiles : %d\n\n",dp[N1][N2]);
	}
}

10130-SuperSale

8092

49.68%

2865

92.11%

10074620

10130

SuperSale

Accepted

C++

0.216

分组01背包问题， 分别计算每个家人能带的最大价值物品，再加起来求总和

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int max(int a,int b){return a>b?a:b;}
int value[1005],cost[1005],group[105];
int dp[30000];
 
int main()
{
 //	freopen("input.txt","r",stdin);
	
	int T,N,G,g,i,j;
	scanf("%d",&T);

	while(T--){
		scanf("%d",&N);
		for(i=1; i<=N; ++i)
			scanf("%d %d",&value[i],&cost[i]);
		scanf("%d",&G);
		for(i=1; i<=G; ++i)
			scanf("%d",&group[i]);

		int maxValue=0;
		for(g=1; g<=G; ++g){
			memset(dp,0,sizeof(dp));
			for(i=1; i<=N; ++i){
				for(j=group[g]; j>=cost[i]; --j)
					dp[j] = max(dp[j-cost[i]]+value[i],dp[j]);
			}
			maxValue += dp[group[g]];
		}
		printf("%d\n",maxValue);
	}
	return 0;
}

10192-Vacation

12967

35.15%

3953

88.24%

10074716

10192

Vacation

Accepted

C++

0.008

2012-05-04 16:06:02

最长公共子序列，本来还以为要不要判断重复的，交了后发现直接A了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


char str1[105],str2[105];
int dp[105][105];

int max(int a,int b){return a>b?a:b;}

 
int main(int i, int j)
{
 //	freopen("input.txt","r",stdin);
	
	int cas=1;
	while(gets(str1+1),gets(str2+1)){
		if(str1[0]=='#') break;
		
		int len1=strlen(str1+1);
		int len2=strlen(str2+1);

		memset(dp,0,sizeof(dp));
	
		for(i=1; i<=len1; ++i){
			for(j=1; j<=len2; ++j){
				if(str1[i]==str2[j]) {
					dp[i][j] = dp[i-1][j-1]+1;
				}
				else{
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
		printf("Case #%d: you can visit at most %d cities.\n",cas++,dp[len1][len2]);
	}

	return 0;
}

357-Let Me Count The Ways

20522

27.54%

5907

66.84%

10074863

357

Let Me Count The Ways

Accepted

C++

0.708

2012-05-04 16:55:01

和674一样。但是特别要注意结果等于1输出格式不一样，还有要用64位int。因为这个原因WA多次

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int value[6]={0,1,5,10,25,50};
long long dp[30005];
long long max(long long a,long long b){return a>b?a:b;}

 
int main(int i, int j)
{
   //	freopen("input.txt","r",stdin);
	int n;
	while(scanf("%d",&n)==1){
			
		for(i=0; i<=n; ++i)
			dp[i]=1;

		for(i=2; i<=5; ++i){
			for(j=value[i]; j<=n; ++j)
				dp[j] += dp[j-value[i]];
		}
		if(dp[n]==1)
			printf("There is only %lld way to produce %d cents change.\n",dp[n],n);
		else 
			printf("There are %lld ways to produce %d cents change.\n",dp[n],n);
	}
	return 0;
}

10465-Homer Simpson

8983

35.24%

2360

82.20%

10075027

10465

Homer Simpson

Accepted

C++

0.260

2012-05-04 17:49:56

这题的题意一开始还搞不懂，后来终于明白了， 设Krusty-burgers有x个，Kwik-e-Mart有y个，

要使m*x+n*y<=t, 即m*x+n*y尽量接近t.如果不等于t，就要输出和t相差多少

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
int dp[10005],cost[2];
int max(int a,int b){return a>b?a:b;}
void swap(int &a,int &b){ int t=a; a=b; b=t; }

int main(int i, int j)
{
 //	freopen("input.txt","r",stdin);
	int m,n,t;
	while(scanf("%d %d %d",&m,&n,&t)!=EOF){
		memset(dp,0,sizeof(dp));
		if(m>n)
			swap(m,n);
		cost[0]=m, cost[1]=n;
		
		for(i=0; i<2; ++i){
			for(j=cost[i]; j<=t; ++j)
				dp[j] = max(dp[j],dp[j-cost[i]]+cost[i]);
		}
 
		int cnt1=dp[t]/m;
		int cnt2=0;

		if(dp[t]==t){
			while(cnt1*m+cnt2*n!=t){
				--cnt1;
				while(cnt1*m+cnt2*n<t)
					++cnt2;
			}
			printf("%d\n",cnt1+cnt2);
		}
		else{
			while(cnt1*m+cnt2*n!=dp[t]){
						--cnt1;
						while(cnt1*m+cnt2*n<dp[t])
							++cnt2;
			}
			printf("%d %d\n",cnt1+cnt2,t-dp[t]);			
		}
	}
	return 0;
}

// 版本2
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
int dp[10005],num[10005],cost[2];
int max(int a,int b){return a>b?a:b;}

int main(int i, int j)
{
//  	freopen("input.txt","r",stdin);
	int m,n,t;
	while(scanf("%d %d %d",&cost[0],&cost[1],&t)!=EOF){
		memset(dp,0,sizeof(dp));
		memset(num,0,sizeof(num));
		
		for(i=0; i<2; ++i){
			for(j=cost[i]; j<=t; ++j){
				if(dp[j-cost[i]]+cost[i]>dp[j]){
					dp[j] = dp[j-cost[i]]+cost[i];
					num[j] = num[j-cost[i]]+1;
				}
				else if(dp[j-cost[i]]+cost[i]==dp[j] && num[j-cost[i]]+1>num[j]){
					num[j] = num[j-cost[i]]+1;
				}
			}
		}
		if(dp[t]==t)
			printf("%d\n",num[t]);
		else
			printf("%d %d\n",num[t],t-dp[t]);
	}
	return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double