HDU 5389 Zero Escape(MUT#8 dp 최적화)
[제목 대의]:
제목:
n개인의 id를 제시하고 두 개의 문이 있는데 각 문에는 하나의 표지가 있다. 우리는 a와 b로 기록한다. 지금 우리는 n사람을 두 조로 나누어 두 개의 문에 들어가서 두 부분의 표지의 화(교체된 구, 한 자릿수가 될 때까지 우리는'구'와'조작'이라고 부른다~)는 각각 a와 b와 같다. 몇 가지 분법이 있는지 묻는다.
【사고방식】: 경기할 때 후배들이 밀어붙이는 방정식이었다. 그때는 dp3차원 dp[i][j]k: 각각 i위, A문, B문의 상태를 나타냈다. 그러나 어떻게 더 최적화해야 할지 몰랐다. 100n의 복잡도에 걸렸다.
시합 후에 문제풀이를 봤는데 (고등학생이 쓴 문제풀이를 보아도 별 소용이 없을 것 같은데~~) 사실 2차원수조로 해결할 수 있다는 것을 발견했어요. 모든 읽은 수조의 합을 계산하면 A, B문과 비교해 보면 J를 더 많이 들 때가 됐어요. 그렇지 않으면 A, B문과 같은 상황을 직접 판단할 수 있어요. ans++, 마지막 답은 ans예요. 너무 약해요. 힘내세요!T_T!
코드:
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#define eps 0.00000001
#define pi acos(-1,0)
#define pr 999983
using namespace std;
typedef long long LL;
const int MOD=258280327;
int arr[110000]= {0};
int dp[110000][10]= {0};
inline LL read()
{
int c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
return c*f;
}
LL get(LL n){return (n-1)%9+1;}
int main(){
LL t,n,A,B;
t=read();
while(t--){
LL sum=0;
LL ans=0;
memset(dp,0,sizeof(dp));
memset(arr,0,sizeof(arr));
n=read();A=read();B=read();
for(int i=1; i<=n; ++i){ /// get the sum of arr[i]
arr[i]=read();
arr[i]=get(arr[i]);
sum+=arr[i];
}
sum=get(sum);
LL xx=get(A+B); /// judge the sum and xx
if(sum==xx){
dp[1][arr[1]]=1; /// dp[i][j]: i j
for(int i=2; i<=n; ++i){
for(int j=1; j<=9; ++j){
int k=j-arr[i];
if(k<=0) k+=9;
dp[i][j]=(dp[i-1][k]+dp[i-1][j])%MOD;
}
}
ans=(dp[n][A]+dp[n][B])%MOD;
printf("%lld
",ans);
}
else{
if(sum==A) ans++;
if(sum==B) ans++;
printf("%lld
",ans%MOD);
}
} return 0;
}
/*
Sample Input
4
3 9 1
1 2 6
3 9 1
2 3 3
5 2 3
1 1 1 1 1
9 9 9
1 2 3 4 5 6 7 8 9
Sample Output
1
0
10
60
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.