ZOJ 3685 ZJU 2013 년 01 월 월 드 컵 J 문제 큐 브
9480 단어 cube
이 문 제 는 DP 를 포함 하여 아무것도 두서 가 없 는 다른 많은 생각 을 하기 시작 했다.당시 에는 40 여분 이 남 았 는데,이 문제 에 전념 하고 싶 었 다.
그리고 복잡 도가 O(2^n)인 프로그램 을 써 서 앞의 25 개 를 계산 해 보 니 15 번 째 부터 답 이 0 이 아니면 1 이 었 다.
분석 해 보면 양음 호 를 바 꾸 고 결과 의 패 리 티 를 바 꾸 지 않 는 다 는 것 을 알 수 있다.1~n 에서 홀수 가 홀수 일 때 답 은 홀수 이 고 그렇지 않 으 면 짝수 이다.
계산 가능 1^3+2^3+...+n^3=n^2*(n+1)^2/4
n>=15 시 에 답 이 0 이 아니면 1 이라는 점 이 성립 되 며,등가 는 1^3 이다. , 2^3,3^3,...............................................................................
정수 분할 문제!!물론 dp 방법 으로 할 수 는 없습니다.해 보 겠 다 는 마음 에 누 드 dfs 를 쓰 고 지 났 습 니 다.이것 은 해 의 수량 이 매우 많다 는 것 을 설명 하 는 것 일 것 이다.
n<15 의 모든 상황 을 폭력 적 으로 계산 할 수 있 습 니 다.저 는 직접 시 계 를 쳐 서 프로그램 에 썼 습 니 다.
물론,나 는 지금 왜 14 보다 클 때 반드시 해 가 있 는 지 증명 할 수 없다.찾 으 면 여기에 추 가 될 것 이다.
코드 는 다음 과 같 습 니 다:
1 #include<cstdio>
2 #include<cstring>
3 using namespace std;
4 typedef long long ll;
5 const char ans[20][20]={
6 "",
7 "+",
8 "-+",
9 "-++",
10 "-+++",
11 "-++++",
12 "-+++-+",
13 "+---+++",
14 "+--+--++",
15 "+--+-+--+",
16 "-+-+++++++",
17 "-++-+--++++",
18 "+--++---+-++",
19 "--+++++-+++++",
20 "-++-+--++--+-+"
21 };
22 char s[10010];
23 ll s3[10010];//
24 bool dfs(ll sum,int n){
25 for(int i=n;i>0;i--)if(sum>=s3[i]){
26 if(sum - s3[i]==0 || dfs(sum - s3[i],i-1)){
27 s[i-1]='+';
28 return true;
29 }
30 }
31 return false;
32 }
33 void solve(ll n){
34 for(int i=0;i<n;i++)s[i]='-';
35 ll sum=n*n*(n+1)*(n+1)/8;
36 dfs(sum,n);
37 for(int i=n-1;i>=0;i--)putchar(s[i]);
38 puts("");
39 }
40 int main()
41 {
42 for(ll i=1;i<=10000;i++) s3[i]=i*i*i;
43 int n;
44 while(~scanf("%d",&n)){
45 if(n<15)puts(ans[n]);
46 else solve(n);
47 }
48 return 0;
49 }이번 달 경 기 를 할 때 마지막 2 분 에 빼 서 죽 였 어 요.상쾌 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CSS배틀 | #19 큐브CSSBattle Challenges에 오신 것을 환영합니다! 이 짧은 기사에서는 챌린지에 대한 솔루션을 살펴봅니다. 내 사고 과정과 구현 세부 사항에 대한 더 나은 통찰력을 얻으려면 아래 코드 조각을 참조하십시오....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
