首页 > 代码库 > hdu1085(求出最小不连续的值)
hdu1085(求出最小不连续的值)
题目意思:
给出面值为1、2、5的个数n1,n2,n3求出最小不连续的值
http://acm.hdu.edu.cn/showproblem.php?pid=1085
题目分析:
方法一、多重背包问题的变形,状态转化方程为
if(a[i]==1) a[i+j*v]=1; (0<j<num[i],v为面值的值,v表示个数)
方法二、由于数据较小直接暴力
对于每一个值,从0到n模拟所有价值,并记录这个值,可以满足
AC代码:
/**
*1、类似背包问题
*if(a[i]==1) a[i+j*v]=1;(0<j<num[i],v为数值)
*2、暴力(由于数据较小可以直接暴力)
*/
#include<iostream>
#include<cstring>
using namespace std;
int a[8005];
/**
int main()//DP
{
int num[3],v[3]={1,2,5};
while(cin>>num[0]>>num[1]>>num[2]){
if(num[0]==0&&num[1]==0&&num[2]==0) break;
memset(a,0,sizeof(a));
int k,sum=0;
for(int i=0;i<3;i++){
sum+=num[i]*v[i];//计算最大数值
}
//cout<<sum<<endl;
a[0]=1;
for(int i=0;i<3;i++){//DP算法
for(int k=sum;k>=v[i];k--){
for(int j=1;j<=num[i];j++){
if(k-v[i]*j>=0) a[k]=a[k-v[i]*j];//当前状态取决于前一状态
}
}
}
for(int k=1;k<=sum+1;k++){//这里不能用sum
if(!a[k]){
cout<<k<<endl; break;
}
}
}
return 0;
}**/
int main()//暴力方法
{
int n,m,l;
while(cin>>n>>m>>l){
if(n+m+l==0) break;
memset(a,0,sizeof(a));
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=l;k++){
a[i*1+j*2+k*5]=1;
}
}
}
for(int k=1;k<=8001;k++){//这里不能用sum
if(!a[k]){
cout<<k<<endl; break;
}
}
}
return 0;
}
hdu1085(求出最小不连续的值)