[각종 면접 문제] 보드게임 확장

2299 단어
제목 설명:
현재 8 * 8 의 바둑판 이 있 습 니 다. 그 위 에 64 개의 서로 다른 가치 의 선물 이 놓 여 있 습 니 다. 작은 바둑판 마다 선물 (선물의 가 치 는 0 보다 100 보다 작 습 니 다) 을 놓 고 한 사람 은 바둑판 의 왼쪽 상단 에 있 습 니 다. 매번 그 는 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있 고 바둑판 에 있 는 선물 을 가 져 가서 바둑판 의 오른쪽 아래 에 있 습 니 다.바둑판 의 왼쪽 상단 에서 오른쪽 하단 으로 이동 할 때 매번 그 는 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있 고 바둑판 에 해당 하 는 선물 을 가 져 갈 수 있 습 니 다. 그러나 받 은 모든 선물 의 가 치 는 하나의 한정 치 limit 보다 크 지 않 습 니 다. 알고리즘 을 설계 하여 제한 치 limit 을 초과 하지 않 는 최대 가 치 를 가 진 선물 을 받 을 수 있 도록 하 십시오.
입력:
여러 개의 테스트 용례 를 입력 하 십시오. 각 테스트 용례 는 모두 9 줄 입 니 다. 첫 번 째 줄 은 제한 값 limit < = 1000 입 니 다. 아래 에는 8 줄 8 열 이 있 습 니 다. i 줄 의 j 열 숫자 는 이 바둑판 의 선물 가 치 를 대표 하고 두 숫자 사이 에 빈 칸 으로 구분 합 니 다.
출력:
각 그룹의 테스트 용례 에 대해 제한 치 limit 를 초과 하지 않 는 최대 가 치 를 얻 을 수 있 는 선물 을 출력 하 십시오.조건 에 맞 는 라인 이 없 으 면 출력 - 1.
샘플 입력:
90
4 2 5 1 3 8 9 7
4 5 2 3 7 1 8 6
7 2 1 8 5 9 3 6
2 8 9 5 6 3 1 7
1 2 4 5 3 7 9 6
3 5 7 8 9 6 2 4
10 8 1 4 7 5 3 9
7 4 6 2 1 3 9 8

샘플 출력:
90

가방 을 추가 하면 됩 니 다. 8 * 8 * 1000 은 배열 을 굴 리 지 않 아 도 됩 니 다. 이 복잡 도 는 직접 폭력 으로 쉽게 hold 할 수 있 습 니 다.
문 제 를 읽 는 것 은 만약 에 도착 하지 못 하면 출력 - 1 이 므 로 현재 칸 의 왼쪽 과 위의 두 칸 이 모두 도착 하지 못 하면 자신 도 도착 하지 못 할 것 이 라 고 판단 해 야 합 니 다. 그렇지 않 으 면 가방 업 데 이 트 를 다시 할 것 입 니 다.
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=8;
int dp[N+1][N+1][1005];
int grid[N+1][N+1];

int main()
{
	memset(dp,0,sizeof(dp));
	int limit;
	while(scanf("%d",&limit)!=EOF)
	{
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				scanf("%d",&grid[i][j]);
				for(int t=0;t<=limit;t++)
					dp[i][j][t]=0;
			}
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				for(int t=0;t<grid[i][j];t++)
					dp[i][j][t]=0;
				for(int t=grid[i][j];t<=limit;t++)
				{
					if(i==1&&j==1)
					{
						dp[i][j][t]=grid[i][j];
						continue;
					}
					if(dp[i-1][j][t-grid[i][j]]==0&&dp[i][j-1][t-grid[i][j]]==0)
						dp[i][j][t]=0;
					else
						dp[i][j][t]=max(dp[i-1][j][t-grid[i][j]],dp[i][j-1][t-grid[i][j]])+grid[i][j];
				}
			}
		}
		int ans =dp[N][N][limit];
		if( ans==0 )
			printf("-1
");
		else
			printf("%d
",ans);
	}
}
C#를 사용하여 직렬 정보 읽는 방법
볼록 다각형 의 최 적 화 된 삼각형 분할 문제

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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