SRM 573 div2
500...
1000
시합할 때 생각이 없다.Trick이 생각났어요. cha를 하고 싶었는데 방에 제출하는 사람이 없었어요...
한 점에서 다른 점으로 m보를 걷는 데 필요한 상황수만 미리 처리하고 dp 공간의 복잡도가 너무 높다는 것을 발견했다.오늘 다른 사람이 어떻게 미리 처리했는지 봤는데 난 아직 너무 어려...
dp[dx][dy][m]는 m보 좌표를 따라 (dx,dy)의 모든 상황수를 이동한 것을 나타낸다.
기억화 검색해봐.
const int MAXN = 55;
const int MOD = 1e9+7;
int dp[MAXN][MAXN][MAXN];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
class WolfPackDivTwo {
public:
int dfs(int dx, int dy, int m) {
if(dp[dx][dy][m] != -1) return dp[dx][dy][m];
int res = 0;
if(m == 0) {
res = (dx == 0 && dy == 0);
} else {
for(int i = 0; i < 4; ++i) {
int xx = abs(dx + dir[i][0]);
int yy = abs(dy + dir[i][1]);
if(xx + yy > m - 1) continue;
res = (res + dfs(xx, yy, m - 1))%MOD;
}
}
return dp[dx][dy][m] = res;
}
int calc(vector <int> x, vector <int> y, int m) {
int n = x.size(), tx, ty, i, ans = 0;
CL(dp, -1);
for(tx = x[0] - m; tx <= x[0] + m; ++tx) {
for(ty = y[0] - m; ty <= y[0] + m; ++ty) {
int tmp = 1;
for(i = 0; i < n; ++i) {
int dx = abs(tx - x[i]);
int dy = abs(ty - y[i]);
if(dx + dy > m) {tmp = 0; continue;}
tmp = (tmp*dfs(dx, dy, m))%MOD;
}
ans = (ans + tmp)%MOD;
}
}
return ans;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
