当前位置:编程学习 > html/css >>

rnqoj-94-飙车-dp

动态规划的题目。
假如所有的车都是不动的。
那么就相当于我的车一次跑三个格,那么状态转移就出来了。
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; }

 


补充:web前端 , HTML/CSS  ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,