一道简单的dp题目

dp[k][i]表示目前第i位是k批次进入吃饭的

直接转移就行了

要倒着扫一遍

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=30000;inline int read(){	int x=0,f=1,ch=getchar();	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}	return x*f;}int n;short a[MAXN];int dp[3][MAXN];int main(){	n=read();	for(int i=0;i
         
          =0;i--){		dp[0][i]=dp[0][i+1];		dp[1][i]=min(dp[0][i+1],dp[1][i+1]);		dp[2][i]=min(dp[2][i+1],dp[1][i+1]);		dp[2][i]=min(dp[0][i+1],dp[2][i]);		++dp[0][i];++dp[1][i];++dp[2][i];--dp[(int)a[i]][i];	}	ans=min(ans,min(dp[0][0],min(dp[1][0],dp[2][0])));	printf("%d\n",ans);	return 0;}