首页 > 代码库 > 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