首页 > 代码库 > hdu_1003_Max Sum hdu_1058_Humble Numbers hdu_1059_Dividing

hdu_1003_Max Sum hdu_1058_Humble Numbers hdu_1059_Dividing

hdu_1003_Max Sum

http://acm.hdu.edu.cn/showproblem.php?pid=1003

题目大意是给出一组数,求出这组数的一个最大的连续子序列的和,并且要求出序列的左右区间。

这道题不会做,膜拜后的思想是,一个连续序列s要加上一个数a,除非该连续序列s的sum已经>0,否则a可以独立成一个序列s‘。于是,用maxsum记录最大的序列和,l和r记录左右区间。

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

#define INF 10000000

int main (){
	int C;
	cin>>C;
	for (int c=1;c<=C;c++){
		int n,s=1,e=1;
		int a[100010],dp[100010];
		memset(dp,0,sizeof(dp));
		cin>>n;a[0]=0;
		for (int i=1;i<=n;i++){
			cin>>a[i];
		}
		int maxsum=-INF,sum=0,left=1;
		for (int i=1;i<=n;i++){
			sum+=a[i];
			if (sum>maxsum){
				maxsum=sum;
				s=left;
				e=i;
			}
			if (sum<0) {
				sum=0;
				left=i+1;
			}
		}
		if (c-1) cout<<endl;
		cout<<"Case "<<c<<":"<<endl;
		cout<<maxsum<<" "<<s<<" "<<e<<endl;
	}
	return 0;
}

hdu_1058_Humble Numbers
http://acm.hdu.edu.cn/showproblem.php?pid=1058

一个数的素因子只由2,3,5,7组成,则叫这个数为humble number,序列有:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ...

现在给你一个数n,要求输出第n个humble number;第1个humble number是1;

(本地暴力打表一分多钟算出5842个humble number,输出到 xxx.txt 里,然后copy数字到代码里存成数组,然后就可以直接输出来了。呵呵。我第一次AC就是这样);

呵呵:

一个数是humble number,那么这个数除以2,3,5,7也是humble number,反之,已知一个humble number序列,那么他的下一个humble number一定是该序列的某个数乘以2,3,5,7的某个数。

如此:dp[i] = min ( { dp[0] ... dp[i-1] } * {2,3,5,7} > dp[i-1] );这样先求出签5842个存到dp[]里。

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

int main(){
	long long dp[5850];
	long long a[]={2,3,5,7};
	dp[0]=1;
	long long minx;
	for (int i=1;i<5842;i++){
		minx=dp[i-1]*2;
		for (int j=i-2;j>=0;j--){
			if (dp[j]*7<dp[i-1]) break;
			for (int k=0;k<4;k++){
				if ((dp[j]*a[k])>dp[i-1]){
					minx=min(minx,dp[j]*a[k]);
				}
			}
		}
		dp[i]=minx;
	}
	int n;
	while (scanf ("%d",&n)!=EOF){
		if (n!=0){

			int a;int b;int i;int v=n;
			{
				char s[][5]={"st","nd","rd","th",""};
				a=n%10;
				n/=10;
				b=n%10;
				if (b==1) i=3;
				else{
					if (a==1) i=0;
					else if (a==2) i=1;
					else if (a==3) i=2;
					else i=3;
			 	}

				cout<<"The "<<v<<s[i]<<" humble number is ";
			}
			cout<<dp[v-1]<<"."<<endl;
		}
		else break;
	}
	return 0;

}

hdu_1059_Dividing

http://acm.hdu.edu.cn/showproblem.php?pid=1059

就这题思路还算清晰 =。=

一堆货物分为6类价值分别是1~6;第i类有ni个。问是否可以平均分成总价值相等的两类。

一个简单的多重背包问题,价值等于重量,dp[i]表示是否可以凑凑价值为i。如果dp[sum/2]=1;则可以dividing,(sum为1~6的总价值量,前提是sum%2==0);

多重背包可行性,use数组记录使用情况。

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

int dp[420010];
int use[420010];

int main()
{
	// freopen ("g.txt","r",stdin);
	int a[6];
	int flag=1;
	int sum;
	int c=0;
	while (flag){
		c++;
		memset(dp,0,sizeof(dp));
		flag=0;sum=0;
		for (int i=0;i<6;i++){
			cin>>a[i];
			if (a[i]){
				flag=1;
			}
			sum+=a[i]*(i+1);
		}
		dp[0]=1;
		for (int i=0;i<6;i++){
			memset(use,0,sizeof(use));
			for (int j=i+1;j<=sum/2;j++){
				if (!dp[j]&&dp[j-(i+1)]&&use[j-(i+1)]<a[i]){
					dp[j]=1;
					use[j]=use[j-(i+1)]+1;
				}
			}
		}
		/*for (int i=0;i<=sum/2;i++){
			cout<<dp[i]<<" ";
		}cout<<endl;*/
		if (flag==0) continue;
		cout<<"Collection #"<<c<<":"<<endl;
		if (dp[sum/2]==1&&sum/2*2==sum){
			cout<<"Can be divided."<<endl;
		}
		else cout<<"Can't be divided."<<endl;
		cout<<endl;
	}
	return 0;
}

dp我水题不水=。=



hdu_1003_Max Sum hdu_1058_Humble Numbers hdu_1059_Dividing