AOJ 2427: hosonagaitokoro

ほそながかった...

通過の順番をそれぞれ決めて後は到着時刻を合わせるようにずらすのを収束するまでやる。収束しなかったらそれは無理配置。
この問題は問題文を何度も読んだことがあるけど、読むたびに誤読している。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long p[10];
long long q[10];
struct wolf{
	int p[5];
	wolf(){}
};
wolf now[6];
int N,M;
int rev[10][10];
int perm[10][10];
long long INF=9999999999999999LL;
long long t[10][10];
long long dfs(int a){
	if(a==M){
		for(int i=0;i<=M+1;i++){
			for(int j=0;j<N;j++){
				t[i][j]=j+p[j]*q[i];
			}
		}
		int cnt=0;
		while(1){
			bool chg=false;
			for(int i=0;i<=M;i++){
				for(int j=0;j<N;j++){
					for(int k=j+1;k<N;k++){
						if(t[i][now[i].p[j]]+p[now[i].p[j]]*(q[i+1]-q[i])>t[i][now[i].p[k]]+p[now[i].p[k]]*(q[i+1]-q[i])){
							chg=true;
							t[i][now[i].p[k]]=t[i][now[i].p[j]]+p[now[i].p[j]]*(q[i+1]-q[i])-p[now[i].p[k]]*(q[i+1]-q[i]);
							for(int l=0;l<=M+1;l++)t[l][now[i].p[k]]=t[i][now[i].p[k]]+p[now[i].p[k]]*(q[l]-q[i]);
						}
						if(t[i][now[i].p[j]]>t[i][now[i].p[k]]){
							chg=true;
							t[i][now[i].p[k]]=t[i][now[i].p[j]];
							for(int l=0;l<=M+1;l++)t[l][now[i].p[k]]=t[i][now[i].p[k]]+p[now[i].p[k]]*(q[l]-q[i]);
						}
						if(i==0&&t[i][now[i].p[j]]>=t[i][now[i].p[k]]){
							chg=true;
							for(int l=0;l<=M+1;l++)t[l][now[i].p[k]]=t[i][now[i].p[j]]+1+p[now[i].p[k]]*(q[l]-q[i]);
						}
					}
				}
			}
			cnt++;
			if(cnt==200)return INF;
			//long long tmp=0;
			//for(int i=0;i<N;i++)tmp=max(tmp,t[M+1][i]);
			//printf("%lld\n",tmp);
			if(!chg)break;
		}
		long long ret=0;
		for(int i=0;i<N;i++)ret=max(ret,t[M+1][i]);
		/*if(ret==382){
			for(int i=0;i<=M;i++){
				for(int j=0;j<N;j++)printf("%d ",now[i].p[j]);
				printf("\n");
			}
			for(int i=0;i<=M+1;i++){
				for(int j=0;j<N;j++)printf("%lld ",t[i][j]);
				printf("\n");
			}
		}*/
		return ret;
	}
	long long ret=INF;
	for(int i=0;i<N;i++){
		perm[a][i]=i;
		rev[a][now[a].p[i]]=i;
	}
	do{
		bool ok=true;
		for(int i=0;i<N;i++){
			if(rev[a][perm[a][i]]>i+1)ok=false;
			if(rev[a][perm[a][i]]<i-1)ok=false;
			for(int j=i+1;j<N;j++){
				if(rev[a][perm[a][i]]>rev[a][perm[a][j]]&&p[perm[a][i]]>=p[perm[a][j]])ok=false;
			}
		}
		if(ok){
			for(int i=0;i<N;i++)now[a+1].p[i]=perm[a][i];
			ret=min(ret,dfs(a+1));
		}
	}while(next_permutation(perm[a],perm[a]+N));
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++)scanf("%lld",p+i);
	scanf("%d",&c);
	N=b;M=c;
	for(int i=0;i<c;i++)scanf("%lld",q+i+1);
	std::sort(q,q+c+1);
	q[c+1]=a;
	for(int i=0;i<b;i++){
		now[0].p[i]=i;
	}
	printf("%lld\n",dfs(0));
}