로곡 P1441 분동 무게 측정(심수+DP)
제목 설명
현재 n개의 분동이 있는데 무게는 각각 a1, a2, a3,......, an이다. m개의 분동을 제거한 후에 최대 몇 개의 다른 무게를 측정할 수 있느냐고 묻는다(0 포함하지 않는다).
입력 출력 형식
입력 형식: 파일 weight.n의 첫 번째 행위는 두 개의 정수 n과 m가 있고 빈칸으로 두 번째 줄을 나누면 n개의 정수 a1, a2, a3,......, an이 있는데 각 분동의 무게를 나타낸다.
출력 형식: 출력 파일 weight.out은 최대 무게를 측정할 수 있는 정수 1개만 포함합니다.
출력 샘플 가져오기
샘플 입력: 3 1 1 2 2
출력 예제: 3
설명
【예시설명】 무게가 2인 분동을 제거한 후 1, 2, 3의 총 3가지 무게를 측정할 수 있다.
[데이터 규모] 20%의 데이터에 대해 m=0;50%의 데이터에 대해 m≤1;50%의 데이터에 대해 n≤10;100% 데이터에 대해 n≤20, m≤4, m≥n,ai≤100.
할 말 없지.. 일단 샅샅이 뒤지고 가방으로 수량을 집계하자.
#include
#include
#include
bool f[2010];
int n,m,ans;
int a[23];
bool v[23];
int max(int x,int y)
{
return x>y?x:y;
}
void dp()
{
memset(f,false,sizeof(f));f[0]=true;
int tot=0,num=0;
for(int i=1;i<=n;i++)
{
if(!v[i]) continue;
for(int j=tot;j>=0;j--)
if(f[j] && !f[j+a[i]]) f[j+a[i]]=true,num++;
tot+=a[i];
}
ans=max(ans,num);
}
void dfs(int yx,int ys)
{
if(ys>m) return;
if(yx>n)
{
if(ys==m) dp();
return;
}
dfs(yx+1,ys);
v[yx]=false;
dfs(yx+1,ys+1);
v[yx]=true;
}
int main()
{
memset(v,true,sizeof(v));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,0);
printf("%d",ans);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 7508황후·(2)+예처리+귀속#include #include #include #include #include #include #include #include #include #include #include #include #include usi...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.