hdu 5110 Alexandra and COS(dp)
hdu 5110 Alexandra and COS
dp와 관련된 것으로 한눈에 알 수 있지만 제목이 준 데이터 양의 범위는 사람을 놀라게 하기 쉽다.문제풀이 방법이 정말 실행 가능한 것 같아...
제목의 뜻에 따라 통계하고자 하는 점은 정북방향 45도 정도의 부채 안에 있다.dp[i][j][k]를 설정하면 관찰점 좌표가 i, j이고 값이 k임을 나타낸다.
k<=sqrt(n)
dp[i][j][k] = dp[i-k][j-k][k] + dp[i-k] [j+k] - dp[i-2*k] [j][k] + 제i행 구간 [j-k, j+k] 내의 포인트
이 공식은 대략적인 추이 방향만 나타내고 일부 변각각의 상황(예를 들어 im 등)은 여전히 참작하여 처리해야 한다.
k > sqrt(n)
폭력적 해결#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1010;
const int M = 35;
typedef long long LL;
int dp[N][N][M], mp[N][N];
char da[N][N];
int n, m, q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
while (scanf("%d%d%d", &n, &m, &q) != EOF)
{
int d = sqrt(double(n));
for (int i = 1; i<= n; ++i)
scanf("%s", da[i]+1);
for (int i = 1; i<= n; ++i)
{
for (int j = 1; j<= m; ++j)
{
mp[i][j] = mp[i][j-1] + (da[i][j]=='X');
}
}
for (int i = 1, *p, kk; i<= n; ++i)
{
for (int j = 1; j<= m; ++j)
{
for (int k = 1; k<= d; ++k)
{
kk = k<<1;
p = &dp[i][j][k];
*p = (da[i][j]=='X');
if (i > k)
{
if (j>k)
{
*p += dp[i-k][j-k][k] + mp[i-k][j] - mp[i-k][j-k];
}
else
{
*p += mp[i-k][j];
if (i > kk) *p += dp[i-kk][j][k] + mp[i-kk][j-1];
}
if (j+k <= m)
{
*p += dp[i-k][j+k][k] + mp[i-k][j+k-1] - mp[i-k][j];
}
else
{
*p += mp[i-k][m] - mp[i-k][j];
if (i > kk) *p += dp[i-kk][j][k] + mp[i-kk][m] - mp[i-kk][j];
}
if (i > kk) *p -= dp[i-kk][j][k];
}
}
}
}
for (int i = 0; i< q; ++i)
{
int r, c, w, res;
scanf("%d%d%d", &r, &c, &w);
if (w > d)
{
res = 0;
for (int j = r, lf=c, rt=c; j >0; j-=w, lf=max(lf-w,1), rt=min(m,rt+w))
res += mp[j][rt]-mp[j][lf-1];
printf("%d
", res);
}
else
printf("%d
", dp[r][c][w]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
k > sqrt(n)
폭력적 해결
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1010;
const int M = 35;
typedef long long LL;
int dp[N][N][M], mp[N][N];
char da[N][N];
int n, m, q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
while (scanf("%d%d%d", &n, &m, &q) != EOF)
{
int d = sqrt(double(n));
for (int i = 1; i<= n; ++i)
scanf("%s", da[i]+1);
for (int i = 1; i<= n; ++i)
{
for (int j = 1; j<= m; ++j)
{
mp[i][j] = mp[i][j-1] + (da[i][j]=='X');
}
}
for (int i = 1, *p, kk; i<= n; ++i)
{
for (int j = 1; j<= m; ++j)
{
for (int k = 1; k<= d; ++k)
{
kk = k<<1;
p = &dp[i][j][k];
*p = (da[i][j]=='X');
if (i > k)
{
if (j>k)
{
*p += dp[i-k][j-k][k] + mp[i-k][j] - mp[i-k][j-k];
}
else
{
*p += mp[i-k][j];
if (i > kk) *p += dp[i-kk][j][k] + mp[i-kk][j-1];
}
if (j+k <= m)
{
*p += dp[i-k][j+k][k] + mp[i-k][j+k-1] - mp[i-k][j];
}
else
{
*p += mp[i-k][m] - mp[i-k][j];
if (i > kk) *p += dp[i-kk][j][k] + mp[i-kk][m] - mp[i-kk][j];
}
if (i > kk) *p -= dp[i-kk][j][k];
}
}
}
}
for (int i = 0; i< q; ++i)
{
int r, c, w, res;
scanf("%d%d%d", &r, &c, &w);
if (w > d)
{
res = 0;
for (int j = r, lf=c, rt=c; j >0; j-=w, lf=max(lf-w,1), rt=min(m,rt+w))
res += mp[j][rt]-mp[j][lf-1];
printf("%d
", res);
}
else
printf("%d
", dp[r][c][w]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
