블 루 브리지 컵 PREV-28 지하 궁전 보물 획득(dp)

13930 단어 #동적 계획블 루 브리지 컵
제목 링크:http://lx.lanqiao.cn/problem.page?gpid=T120 사고:1.d p[i][j][a][b]dp[i][j][a][b]dp[i][a][b]좌 표를(i,j)(i,j)(i,j)(i,j)위치 로 가기 위해 손 에 a a a 개의 물품 이 있 고 모든 물품 중 최대 치 는 b b b 의 방안 수 를 기록 합 니 다.2.우리 가 지금(a,b)(a,b)(a,b)(x,y)(x,y)(x,y)(x,y)(이 두 위치 가 인접 해 있다 고 가정 하면 v[i][j]v[i][j]v[i][j]가 좌표(i,j)(i,j)(i,j)(i,j)에 있 는 물품 의 가치 라면(x,y)(x,y)(x,y)(x,y)(x,y)는 이 위 치 를 취하 지 않 는 물품 을 선택 할 수 있다.만약 에 이 위치 물품 이(a,b)(a,b)보다 크 면 물품 의 최대 치,그럼 이곳 의 아 이 템 을 선택 할 수도 있 습 니 다.복잡 도 O(n m k C)O(nmkC)O(nmkC)코드:
#include

using namespace std;

const int mod = 1000000007;
int n, m, k, v[55][55];
int dp[55][55][15][15];

#define f(a, b) a = (a + b) % mod;
inline void check(int a, int b, int & x, int & y) {
	if(a <= 0 || b <= 0) return;
	for(int	i = 0; i <= k; i++) {
		for(int j = 0; j <= 13; j++) {
			f(dp[x][y][i][j], dp[a][b][i][j]);
			if(v[x][y] > j) f(dp[x][y][i + 1][v[x][y]], dp[a][b][i][j]);
		}
	}
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			scanf("%d", &v[i][j]);
			++v[i][j];	
		}
	}
	dp[1][1][0][0] = 1;
	dp[1][1][1][v[1][1]] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			check(i - 1, j, i, j);
			check(i, j - 1, i, j);
		}
	}
	int ans = 0;
	for(int i = 1; i <= 13; i++) f(ans, dp[n][m][k][i]);
	printf("%d", ans);
	return 0;	
}
자바 로 mp3 파일 재생 시간 과 tag 정 보 를 가 져 옵 니 다.
hdu 3061 전투 최대 권 폐쇄 도

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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