POJ1088 스키 기억화 검색
2528 단어 DP
폭력은 가지치기만 하면 지나칠 줄 알았더니 폭력을 노려쓴다==
앞사람의 실패를 거울로 삼다.
Problem: 1088 User: BPM136
Memory: N/A Time: N/A
Language: G++ Result: Time Limit Exceeded
#include
#include
#include
#include
#include
#include
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline LL read()
{
LL d=0,f=1;char s=getchar();
while(s'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
#define N 105
#define MAX 1000000000
int a[N][N];
int f[N][N];
int n,m,ans=1;
int pre[4][2];
void getpre()
{
int cnt=0;
fo(i,-1,1)
fo(j,-1,1)
if(abs(i-j)==1)
{
pre[cnt][0]=i;pre[cnt++][1]=j;
}
}
//int v[N][N];
void dfs(int x,int y,int val,int anss)
{
if(x<1||y<1||x>n||y>m)return;
// if(v[x][y]==1)return;
if(a[x][y]>=val||f[x][y]>anss)return;
int cost=anss+1;ans=max(ans,cost);
f[x][y]=max(f[x][y],anss);//v[x][y]=1;
fo(i,0,3)
dfs(x+pre[i][0],y+pre[i][1],a[x][y],cost);
// v[x][y]=0;
}
int main()
{
getpre();
n=read(),m=read();
fo(i,1,n)
{
fo(j,1,m)
a[i][j]=read();
}
fo(i,1,n)
{
fo(j,1,m)
{
// memset(v,0,sizeof(v));
dfs(i,j,MAX,0);
}
}
cout<
그리고 나는 T를 몇 번 하고 규범적인 기억화 검색을 쓰기로 결정했다==Problem: 1088 User: BPM136
Memory: 804K Time: 32MS
Language: G++ Result: Accepted
#include
#include
#include
#include
#include
#include
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline LL read()
{
LL d=0,f=1;char s=getchar();
while(s'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
#define N 105
#define MAX 1000000000
int a[N][N];
int f[N][N];
int n,m,ans=-1;
int pre[4][2];
void getpre()
{
int cnt=0;
fo(i,-1,1)
fo(j,-1,1)
if(abs(i-j)==1)
{
pre[cnt][0]=i;pre[cnt++][1]=j;
}
}
int dfs(int x,int y)
{
if(f[x][y])return f[x][y];
if(ans==n*m)return 0;
fo(i,0,3)
{
int tx=x+pre[i][0],ty=y+pre[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
{
if(a[tx][ty]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.