HDU FatMouse and Cheese(기억형 검색+dp 마인드)

2806 단어
아이디어:
1) 가장 소박한 사상은 (0,0)에서 모든 가능한 경로를 매거하여 모든 경로의 ans를 구하고 도전을 비교하면 가장 큰 것이 답이다.2) (0,0)에서 출발한 하위 문제는 (x,y)(x>0,y>0)에서 출발한 것으로 각 하위 문제에 대해 독립을 확정하는 것이 가장 좋은 것이 분명하다.그래서 모든 하위 문제를 해결하고 이 문제를 해결했다.
3) dp[x][y]는 (x, y)에서 먹을 수 있는 치즈를 기록하기 때문에 dp[x][y]는 += 경로에 있는 모든 dp[nx][ny]의 치즈이다
4) 문제는 100*100의 그림이 매번 모든 것을 반복해서 열거하는 것은 과장될 수 있다는 것이다.그래서 사실 자주 사용하는 물건인 기억화 검색을 사용할 수 있다.
(x, y)는 현재 위치이고 (nx,ny)는 다음 단계이다. 거슬러 올라갈 때 반드시 (nx,ny)가 생길 것이다. 이때 dfs의 처음에 그에게 표시를 붙인다. 만약에 dp[nx][ny]가 이미 답이 있다면 더 이상 구할 필요가 없다.
if(dp[x][y])  return dp[x][y];

그렇지 않으면 예를 들어 dp[0][0]를 구할 때 반드시 경로상의 값을 다시 한 번 계산해야 하며 중복 계산의 횟수가 무서운 지경에 이르렀다.
이 표지는 기억화 조작이라고도 부른다. 실제적으로 초래된 효과는 중복 조작을 피하고 필요한 조작만 남긴다. 이것은 dfs를 일반적인 몇 층 순환의 dp로 바꾸는 것과 같다.
/* ***********************************************
Author        :angon
************************************************ */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define REP(i,k,n) for(int i=k;i'9'; ch=getchar());
    for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';
    return s;
}
inline void print(int x)
{
    if(!x)return;
    print(x/10);
    putchar(x%10+'0');
}
*/
int n,k,dp[maxn][maxn],mp[maxn][maxn],vis[maxn][maxn];
int dir[][2]={0,1,0,-1,1,0,-1,0};
int dfs(int x,int y)
{
    if(dp[x][y])
        return dp[x][y];
    int temp=0,ans=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<4;j++)
        {
            int nx=x+dir[j][0]*i;
            int ny=y+dir[j][1]*i;
            if(nx>=0 && nx=0 && nymp[x][y])
            {
                vis[nx][ny]=1;  //         ，    
                temp = dfs(nx,ny);
                vis[nx][ny]=0;
                ans = max(ans,temp);
            }
        }
    }
    dp[x][y] = ans + mp[x][y];  //       dp[x][y]，    ,      
    return dp[x][y];
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&k))
    {
        if(n==k && n==-1) break;
        memset(dp,0,sizeof(dp));
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        for(int i=0;i
C-후부 반복 최적화
Storybook으로 더 나은 테스트

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage