[JZOJ1274] 여행의 코스 [DP]

11845 단어 dp

제목 대의:


제목 링크:https://jzoj.net/senior/#main/show/1274우리 곽가는 한동안 원소라는 사람이 큰일을 하는데 몸을 아끼는 것을 발견했다. 작은 이익을 보고 의리를 잊은 데다가 조조가 군대를 모집하고 말을 사기 때문에 원소를 탈출하여 조조에게 투항하기로 결정했다. 우리 조조는 MM일에 좋은 인재를 모집했다. 우리 곽가는 일찍 갈 수도 없고 늦게 갈 수도 없었다. 그래서 그는 이 시간을 틈타 다른 도시를 돌아다녔다. 두 도시 사이에는 마차를 타고 왕래할 수밖에 없었다.우리 곽가는 매우 돈을 탐하기 때문에, 그는 최소한의 비용을 쓰려고 하기 때문에, 우리가 그를 도와 이 최소한의 비용을 구해야 한다.

아이디어:


분명히 2차원 d p dp dp: fi j f{ij}fij는 ii i일에 jj도시에 도착하는 최소 비용을 나타낸다.그러면 분명히 i-3-1i-1i-31일 임의의 도시(이날 마차가 이곳에 도착할 수만 있다면)에서 옮길 수 있다.[i] [j] = mi n(f[i] [j], f[ii 1] [k] + c [k] = m i n (f i] [j] = f [i] [j] [j], f[i] [k] [k] + c [j] [(i-4 1)% T [k] [j] + 1]) f[i] [j], f[[i] [j] [j], f[k] [k] + c [k] + c [j] [(i] [j] [j] [j] [(i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [[j] [j] [j] [j] [T[k][j]+1]) 중 kk는 매거진 i-3-1i-1i-3-1일의 위치이고 TT는 마차 가격이다.시간 복잡도: O(n2m)O(n^2m)O(n2m)로 본 문제를 넘기기에 충분합니다.

코드:

#include 
#include 
#include 
using namespace std;

const int N=110;
const int M=210;
const int Inf=1e9;
int n,m,x,T[N][N],c[N][N][30],f[M][N];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j)
			{
				scanf("%d",&T[i][j]);
				for (int k=1;k<=T[i][j];k++)
				{
					scanf("%d",&c[i][j][k]);
					if (!c[i][j][k]) c[i][j][k]=Inf+1;
				}
			}
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][1]=0;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
			for (int k=1;k<=n;k++)
				if (k!=j)
					f[i][j]=min(f[i][j],f[i-1][k]+c[k][j][(i-1)%T[k][j]+1]);
	if (f[m][n]<Inf) printf("%d
",f[m][n]);
		else printf("0
");
	return 0;
}
효율적인 스택 활용
`Scoped` 패턴을 사용하여 Rails 컨트롤러 간에 공통 코드 공유

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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