[낙곡] P1537 탄주(#검색)
마사와 빌은 각자 자신의 탄주 소장품을 가지고 있다.그들은 두 사람이 탄주를 평등하게 가질 수 있도록 소장품을 재분배하려고 한다.만약 모든 탄주의 가치가 같다면 그들은 동등하게 나눌 수 있을 것이다.불행히도 탄주가 더 크거나 아름다워서 마사와 빌은 탄주마다 1~6의 가치를 주었다.지금 그들은 이 탄주들을 똑같이 나누어 모든 사람이 얻는 총가치를 똑같이 하려고 한다.불행하게도, 그들은 그들이 이런 방식으로 탄주를 나누지 못할 수도 있다는 것을 발견했다.예를 들어 가치가 1, 가치가 3, 두 개의 가치가 4인 탄주가 있다면 그들은 탄주를 가치가 같은 두 부분으로 나눌 수 없다.그래서 그들은 모든 탄주를 가치와 같은 두 부분으로 나눌 수 있는지를 알려주는 프로그램을 쓰기를 원한다.
입력 출력 형식
입력 형식:
입력 파일에는 여러 개의 줄이 있는데, 줄에는 6개의 비음수 N1이 포함되어 있다....,N6, 그중 미는 수치 i의 탄주의 가치다.최대 탄주 총수는 20000에 이를 것이다.
입력 파일의 마지막 행은 0 0 0 0 0 0입니다.이 분야를 처리하지 마라.
출력 형식:
각 세트의 데이터에 대해 "Collection #k:"을 출력하고, k는 여러 번째 세트를 출력하며, 이어서 "Can be divided."또는 "Can't be divided."
각 조가 출력된 후 빈 줄을 하나 더 쳐라.
출력 샘플 가져오기
샘플 #1 입력
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
샘플 내보내기 #1
Collection #1:
Can't be divided.
Collection #2:
Can be divided.사고의 방향
정해는 가방일 텐데, 나는 쓸 줄 몰라.당신들의 동태 기획이 그렇게 어려운가요?
정해는 가방이기 때문에 라벨에 가방 dp가 붙습니다.
dfs:
폭력은 탄주 하나하나를 매거해서 두 개의 탄주 총가치의 절반을 모을 수 있는지 확인해 보자.(처음에 내가 쓴 폭력 6중 순환, 이후 줄곧 20점)
#include
#include
#include
using namespace std;
int n,s,a[7],flag;
void dfs(int now,int v)//now ，cnt
{
if(now==s)//
{
v++;// +1
now=0;// =0
if(v==2)// 2
{
flag=1;//
return;
}
}
register int i;
for(i=6;i>=1;i--)//
{
if(a[i] && now+i<=s)// i
{
a[i]--;
dfs(now+i,v);
if(flag)//
{
return;
}
a[i]++;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
register int i,j,k(1);
while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6])
{
flag=0,s=0;
for(i=1;i<=6;i++)
{
s+=a[i]*i;//
}
if(s==0)
{
return 0;
}
cout<>=1;//
dfs(0,0);
if(flag==1)
{
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[낙곡] P2285 [HNOI2004] 두더지 잡기(#선형 dp)n*n의 격자에서 어떤 순간에 두더지는 특정한 격자에서 머리를 내밀어 바람을 쐬곤 한다.너는 로봇을 제어해서 두더지를 잡을 수 있다. 만약 i시간에 두더지가 어떤 격자에 나타나고 로봇도 같은 격자에 있으면 이 두더지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
