조합 수학-모 함수 의 변형-hdu 1171:Big Event in HDU
6093 단어 event
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 24002 Accepted Submission(s): 8458
Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0
Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1
Sample Output
20 10
40 40
Author
lcy
Mean:
n 가지 물품 이 있 고 첫 번 째 물품 의 단 가 는 v1 이 며 수량 은 m1 이다.두 번 째 물품 의 단 가 는 v2 이 고 수량 은 m2 입 니 다..............................................................................
analyse:
이 문제 의 해법 은 매우 많다.dp,모 함수.
여기 서 나 는 두 가지 방법 으로 해 보 았 는데,뒤의 방법 이 모 함수 보다 훨씬 빠르다 는 것 을 발견 하 였 다.
Time complexity：O(n^2)
Source code：
모 함수 코드:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-09-18-18.50
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 234567
#define LL long long
using namespace std;
int val[600],cnt[110];
int c1[N],c2[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);
int n;
while(cin>>n&&n>0)
{
long long sum=0;
for(int i=1;i<=n;++i)
{
cin>>val[i]>>cnt[i];
sum+=val[i]*cnt[i];
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=0;i<=cnt[1]*val[1];i+=val[1])
c1[i]=1;
for(int i=2;i<=n;++i)
{
for(int j=0;j<=sum;++j)
{
for(int k=0;k<=cnt[i];++k)
{
c2[val[i]*k+j]+=c1[j];
}
}
for(int j=0;j<=sum;++j)
{
c1[j]=c2[j];
c2[j]=0;
}
}
if(c1[sum/2]==2)
{
cout<<sum/2<<" "<<sum/2<<endl;
continue;
}
int t=sum/2;
int QAQ,TAT;
int minn=987654321;
for(int i=0;i<=sum;++i)
{
if(c1[i])
{
if(abs(sum/2-i)<minn)
{
minn=abs(sum/2-i);
QAQ=i;
}
}
}
TAT=sum-QAQ;
if(QAQ<TAT)
{
QAQ^=TAT^=QAQ^=TAT;
}
cout<<QAQ<<" "<<TAT<<endl;
}
return 0;
}
수학 방법:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-09-18-23.05
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
int val[N],cnt[N];
int buff[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);
int n;
while(cin>>n&&n>0)
{
long long v,t,idx=0,sum=0;
for(int i=1;i<=n;i++)
{
cin>>v>>t;
val[i]=v,cnt[i]=t;
sum+=val[i]*cnt[i];
while(t--)
{
buff[++idx]=v;
}
}
sort(buff+1,buff+1+idx);
int half=sum/2;
long long ans=0;
for(int i=idx;i>=1;--i)
{
if(ans+buff[i]<=half)
{
ans+=buff[i];
}
}
cout<<sum-ans<<" "<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
앱에서 KSP 출력 사용: 4부이제 생성된 클래스가 있으므로 코드에서 사용해 보겠습니다. Checkout other parts in this series: Android KSP guide for dummies by a Dummy: Part 1 (...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
