Codeforces 398B Painting The Wall(dp)
제목의 대의: n과 m를 제시하면 n*n의 평면에 n*n개의 타일이 있고 그 중 m개의 타일이 이미 색칠되었다는 것을 나타낸다.현재 랜덤으로 한 조각을 선택하여 색칠을 진행합니다(색칠을 건너뛰면 시간도 소모됩니다). 1단계가 소모됩니다.종료 조건은 줄마다 최소한 타일이 칠해져 있는 것이다.마음에 드는 상황으로 바르는 데 시간이 걸린다는 기대를 물어봤다.
문제풀이 사고방식: 현장에서 이 문제를 낼 수 없으니 연습한 것이 너무 적은 것 같다.제목은 줄로 n열을 칠하고 열로 n열을 칠하는 것으로 이해할 수 있다.그러면 dp[i][j]는 줄에 i줄이 아직 바르지 않았고, 열에 j열이 아직 바르지 않은 상황에서 필요한 시간 기대를 나타낸다.그리고 색칠이 끝난 타일마다 등가로 오른쪽 아래로 이동할 수 있다(행수와 열수가 변하지 않는다면).그리고 대체적으로 그림을 4점으로 나눌 수 있는데 왼쪽 상단에 있는 한 조각을 선택하면 줄과 열이 모두 하나 칠해진다.오른쪽 상단에 줄이 하나 칠해져 열이 변하지 않는다.왼쪽 아래쪽의 말은 줄이 변하지 않고 열이 하나 칠해진다.오른쪽 하단에 행렬이 변하지 않는다.
그래서 dp[i][j]=1(어쨌든 시간을 소모해야 한다)+k/(n^2)가 있다.
k = i*j*dp[i-1][j-1] + (n-i)*j*dp[i][j-1] + i*(n-j)*dp[i-1][j] + (n-i)*(n-j)*dp[i][j];
등식 오른쪽에도 미지수 dp[i][j]가 있으니 공식을 간략하게 해야 합니다.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 2005;
int n, m, r, l, x[N], y[N];
double dp[N][N];
void init () {
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
scanf("%d%d", &n, &m);
int a, b;
r = l = n;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
if (x[a] == 0) r--;
if (y[b] == 0) l--;
x[a]++; y[b]++;
}
}
double solve () {
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i-1][0] + n*1.0/i;
dp[0][i] = dp[0][i-1] + n*1.0/i;
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= l; j++) {
dp[i][j] = n * n;
dp[i][j] += i * j * dp[i-1][j-1];
dp[i][j] += i * (n-j) * dp[i-1][j];
dp[i][j] += (n-i) * j * dp[i][j-1];
dp[i][j] /= (n*n - (n-i)*(n-j));
}
}
return dp[r][l];
}
int main () {
init ();
printf("%.10lf
", solve () );
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
