rnqoj-94-飙车-dp - html/css语言栏目：html.css - 自学

动态规划的题目。 假如所有的车都是不动的。 那么就相当于我的车一次跑三个格，那么状态转移就出来了。 dp[i][j]=min(dp[i-2][j-1]+map[i][j],dp[i-2][j]+map[i][j]+map[i-1][j],dp[i-2][j+1]+map[i][j]);  

#include<stdio.h>  
#include<iostream>  
using namespace std;  
int map[1001][13];  
int dp[1001][13];  
int main()  
{  
    int i,j,n,k;  
    char str[1001];  
    while(~scanf("%d%d",&n,&k))  
    {  
        for(i=1;i<=n;i++)  
        {  
            scanf("%s",str);  
            for(j=1;j<=k;j++)  
            {  
                map[i][j]=str[j-1]-'0';  
            }  
        }  
        for(i=1;i<=n+1;i++)  
        {  
            for(j=1;j<=k;j++)  
            {  
                if(i<=2)dp[i][j]=map[i][j];  
                else  
                {  
                    dp[i][j]=dp[i-2][j]+map[i-1][j];  
                    if(j!=1)dp[i][j]=min(dp[i][j],dp[i-2][j-1]);  
                    if(j!=k)dp[i][j]=min(dp[i][j],dp[i-2][j+1]);  
                    dp[i][j]=dp[i][j]+map[i][j];  
                }  
            }  
        }  
        int mins=999999;  
        for(i=1;i<=k;i++)  
        {  
            mins=min(mins,dp[n+1][i]);  
        }  
        cout<<mins<<endl;  
    }  
    return 0;  
}