poj 1014 dividing
3128 단어 poj
대략 제목: 6가지 가치가 있는데 각각 1-6의 광석이...각각 num[i]개가... 두 사람에게 같은 가치의 광석을 나눌 수 있느냐고 물었다.다중 가방에 2진법 최적화 방법.순수한 dp와 dfs가 더 있을 것 같습니다.
우선 총가치가 0이거나 홀수라면 균등하게 나눌 수 없다는 것이 분명하다.나머지 짝수라면 다중 가방, dp[j]로 j의 돌을 장착할 수 있는 최대 가치를 기록합니다.바이너리 최적화도 있어.
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[1000000];
int n[10],ans=1,i,k,j,sum;
int main()
{
while(1)
{
sum = 0;
for(i = 1;i <= 6;i ++)
{
cin>>n[i];
sum += n[i]*i;
}
if(sum==0) break;
if(sum % 2 == 1) printf("Collection #%d:
Can't be divided.
",ans);
else
{
memset(dp,0,sizeof(dp));
sum/= 2;
for(i = 1;i <= 6;i ++)
{
k = 1;
while(n[i] > k)
{
for(j = sum;j >= k * i;j --)
dp[j] = max(dp[j],dp[j-k*i] + k*i);
n[i] -= k;
k *= 2;
}
for(j = sum;j >= n[i] * i;j --)
dp[j] = max(dp[j],dp[j-n[i]*i] + n[i] * i);
}
if(dp[sum] == sum)
printf("Collection #%d:
Can be divided.
",ans);
else
printf("Collection #%d:
Can't be divided.
",ans);
}
ans ++;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
