题目：
分析：
定义dp[i][j]为从 1~i 出去-7~7个人使房间合法的次数，负数表示进去
枚举第i个房间的状态，转移到第j个房间的状态。
#include<bits/stdc++.h> using namespace std; #define ri register int #define N 100005 #define inf 1<<28 int n,a[N],dp[N][22]; bool check(int x) { if(x==0 || x==4 || x==7) return true; return false; } int main() { freopen("hotel.in", "r", stdin); freopen("hotel.out", "w", stdout); scanf("%d",&n); for(ri i=1;i<=n;++i) scanf("%d",&a[i]); for(ri i=0;i<=n;++i) for(ri j=0;j<=20;++j) dp[i][j]=inf; dp[0][7]=0; //dp[i][j]定义的是从1~i出去-7~7个人使房间合法的次数 负数表示进去 for(ri i=0;i<=n-1;++i){ for(ri j=0;j<=14;++j)//美剧当前i的状态 if(dp[i][j]<inf){//如果是一个合法状态 for(ri k=0;k<=14;++k){//枚举i+1的状态 int in=j-7,out=k-7;//in和out得到对于i和i+1这两个阶段真正进出状态(因为下标整体加了7) //in指从i-1到i 对于i来说进来了in个人，out指的是从i到i+1，i出去out个人，i+1进来out个人 if(check(a[i+1]+in-out)) dp[i+1][k]=min(dp[i+1][k],dp[i][j]+abs(in));//i+1的真正状态其实是k-7 整体+7使得状态下标非负 } } } int ans=dp[n][7]; printf("%d\n",ans>=inf ? -1 : ans); } /* 7 1 0 7 0 0 0 3 */