Stone game(2019 ICPC 상하이 스테이션)
Stone game
제목 설명:
CSL loves stone games. He has nnn stones; each has a weight aia_iai. CSL wants to get some stones. The rule is that the pile he gets should have a higher or equal total weight than the rest; however if he removes any stone in the pile he gets, the total weight of the pile he gets will be no higher than the rest. It’s so easy for CSL, because CSL is a talented stone-gamer, who can win almost every stone game! So he wants to know the number of possible plans. The answer may be large, so you should tell CSL the answer modulo 109+710^9 + 7109+7.Formerly, you are given a labelled multiset S={a1,a2,…,an}S={a_1,a_2,\ldots,a_n}S={a1,a2,…,an}, find the number of subsets of SSS: S′={ai1,ai2,…,aik}S’={a_{i_1}, a_{i_2},\ldots, a_{i_k} }S′={ai1,ai2,…,aik}, such that (Sum(S′)≥Sum(S−S′))∧(∀t∈S′,Sum(S′)−t≤Sum(S−S′)).\left(Sum(S’)\ge Sum(S-S’)\right)\land\left(\forall t\in S’, Sum(S’) - t\le Sum(S-S’)\right) .(Sum(S′)≥Sum(S−S′))∧(∀t∈S′,Sum(S′)−t≤Sum(S−S′)).
입력:
The first line an integer TTT (1≤T≤10)1\leq T\leq 10)1≤T≤10), which is the number of cases.For each test case, the first line is an integer nnn (1≤n≤3001\leq n\leq 3001≤n≤300), which means the number of stones. The second line are nnn space-separated integers a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an (1≤ai≤5001\leq a_i\leq 5001≤ai≤500).
출력:
For each case, a line of only one integer ttt — the number of possible plans. If the answer is too large, please output the answer modulo 109+710^9 + 7109+7.
샘플 입력:
2
3
1 2 2
3
1 2 4
샘플 출력:
2
1
샘플 해석
In example 1, CSL can choose the stone 1 and 2 or stone 1 and 3. In example 2, CSL can choose the stone 3.
code:
보존할 방법을 고민하다가 지금 문제를 보충해 봅시다. 이 문제를 생각해 봅시다. 한 무더기의 돌을 한 사람이 그 중에서 한 무더기의 돌을 꺼내서 남은 돌보다 질이 무겁고 그 중에서 이미 꺼낸 돌무더기에서 임의의 돌을 꺼내야 한다는 뜻입니다. 이런 돌무더기는 원래 남은 돌보다 질이 가볍습니다. 그러면 가장 가벼운 돌이 만족하면그러면 다 만족해요.
#include
#include
#include
#include
using namespace std;
const int maxn=355;
const long long mod=1e9+7;
long long dp[maxn*505];
int a[maxn];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int ttt;
scanf("%d",&ttt);
while(ttt--){
int n;
scanf("%d",&n);
memset(dp,0,sizeof(dp));
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
long long ans=0;
dp[0]=1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=sum;j>=a[i];j--){
dp[j]+=dp[j-a[i]];
dp[j]=dp[j]%mod;
if((j>=sum-j)&&(j-a[i]<=sum-j)){
ans+=dp[j-a[i]];
ans=ans%mod;
}
}
}
printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2013 ACMICPC 항주 라이브 I 문제사고방식: 기억화 검색. dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.