P1722 매트릭스 II & P1044 창고 문제풀이
원제 링크 1 1 1 1 1
원제 링크 2, 2, 2.
먼저 P1722\text{P1722} P1722를 살펴보겠습니다.
제목 요약:
하나 있다× n 2\times n 2×n의 격자, 현재 너는 그것들의 모든 칸에 빨간색이나 검은색을 염색해서 모든 칸에 빨간색 칸이 검은색 칸과 똑같이 많아지도록 해야 한다.
n ≤ 100 n\leq 100 n≤100.
데이터 범위가 비교적 작은 이상 우리는 2차원 dp\text{dp}dp를 고려할 수 있다.
fi, jf 로{i,j}fi,j는 앞의 iii칸 염색 jj개의 빨간색 방안 수를 나타낸다.
fi, j = f i -3 1, j + f i -3 1, j -3 1 f{i,j} = f_{i-1,j} + f_{i-1,j-1} fi,j=fi−1,j+fi−1,j−1.
세부사항을 주의 깊게 열거하면 된다.
시간 복잡도: O(n2)\mathcal{O}(n^2)O(n2).
실제 점수: 100p t s 100pts 100pts.
#pragma GCC optimize(2)
#include
using namespace std;
const int N=1e2+1;
const int MOD=100;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
int n,f[N<<1][N<<1];
int main() {
n=read();
f[1][1]=1;
for(int i=2;i<=(n<<1);i++) for(int j=(i+1)>>1;j<=i;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1])%100;
printf("%d
",f[n<<1][n]);
return 0;
}
2배 경험시간: 분석을 통해 창고라는 문제가 본 문제와 똑같다는 것을 발견할 수 있습니다.빨간색을 입고 검은색을 입고 창고를 만들면 된다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.