第一次做动规题目，下面均为个人理解以及个人方法，状态转移方程以及状态的定义也是依据个人理解。请过路大神不吝赐教。
状态：每一列的每个数[ i ][ j ]都是一个状态；
然后定义状态[ i ][ j ]的指标函数d[ i ][ j ]为从[ i ][ j ]向右出发的能够得到的最小的整数和；
状态转移方程：d[ i ][ j ]=min(d[ i+1 ][ j+1 ][ i-1 ][ j+1 ][ i ][ j+1 ])+a[ i ][ j ];
当中a[ i ][ j ]为当前位置的数值；
然后有了这些就能够用自己熟悉的方式对问题求解了。
我所知道的合理求解过程有两种：记忆化搜索和递推。
我所知道的输出方法有两种：在求解过程中记录最优位置并在最后输出。全然在输出过程中寻求最佳位置并输出；
下面是自己写的两种输出不同的方法，其处理求解过程均为递推，我觉得对本题来讲记忆化搜索比較复杂，而递推又显而易见
1.
#include2.#include #include #include using namespace std;typedef long long ll;int m,n;int a[50][1100];int rd[50][1100];ll d[50][1100];ll min_ans(ll t1,ll t2 ,ll t3){ long long temp=min(t1,t2); temp=min(temp,t3); return temp;}int min_pos(ll ans,int y,int x1,int x2,int x3){ int pos=m+1; if(ans==d[x1][y]) { pos=min(pos,x1); } if(ans==d[x2][y]) { pos=min(pos,x2); } if(ans==d[x3][y]) { pos=min(pos,x3); } return pos;}void dp(){ for(int i=n;i>=1;i--) { for(int j=1;j<=m;j++) { int temp1=j-1; if(temp1==0) temp1=m; int temp2=j+1; if(temp2>m) temp2=1; ll t1,t2,t3,ans;int pos; t1=d[temp1][i+1];t2=d[j][i+1];t3=d[temp2][i+1]; d[j][i]=min_ans(t1,t2,t3)+a[j][i]; rd[j][i]=min_pos(d[j][i]-a[j][i],i+1,temp1,j,temp2); } }}void print_ans(int pp){ int cur=1; printf("%d",pp); while(cur!=n) { printf(" %d",rd[pp][cur]); pp=rd[pp][cur]; cur++; }}int main(){ while(scanf("%d%d",&m,&n)!=EOF) { memset(d,0,sizeof(d)); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } dp(); long long min_ = -1; for(int i=1;i<=m;i++) { if(min_==-1) min_=d[i][1]; else min_=min(min_,d[i][1]); } int pp; for(int i=1;i<=m;i++) { if(d[i][1]==min_) { pp=i; break; } } print_ans(pp); printf("\n"); printf("%lld",d[pp][1]); printf("\n"); } return 0;}
#include#include #include using namespace std;typedef long long ll;int m,n;int a[50][1100];int rd[50][1100];ll d[50][1100];ll min_ans(ll t1,ll t2 ,ll t3){ long long temp=t1>t2?
t2:t1; return temp>t3?t3:temp; } void dp() { for(int i=n; i>=1; i--) { for(int j=1; j<=m; j++) { int temp1=j-1; if(temp1==0) temp1=m; int temp2=j+1; if(temp2>m) temp2=1; ll t1,t2,t3,ans; int pos; t1=d[temp1][i+1]; t2=d[j][i+1]; t3=d[temp2][i+1]; d[j][i]=min_ans(t1,t2,t3)+a[j][i]; } } } void print_ans(int pp,int cur) { printf("%d",pp); cur++; while(1&&cur<=n) { int i; for(i=1; i<=m; i++) { if((d[i][cur]==d[pp][cur-1]-a[pp][cur-1])) { if(pp==1&&(i==m||i==pp||i==pp+1)) { printf(" %d",i); break; } else if(pp==m&&(i==1||i==pp||i==pp-1)) { printf(" %d",i); break; } else if(i>=pp-1&&i<=pp+1) { { printf(" %d",i); break; } } else continue; } } pp=i; cur++; if(cur>n) break; } } int main() { while(scanf("%d%d",&m,&n)!=EOF) { memset(d,0,sizeof(d)); for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { scanf("%d",&a[i][j]); } } dp(); long long min_ = -1; for(int i=1; i<=m; i++) { if(min_==-1) min_=d[i][1]; else min_=min(min_,d[i][1]); } int pp; for(int i=1; i<=m; i++) { if(d[i][1]==min_) { pp=i; break; } } print_ans(pp,1); printf("\n"); printf("%I64d",d[pp][1]); printf("\n"); } return 0; }
第一次做动规题目，花了好久才做好，由于期间出了一些小错误（如今看来依然是一些细节上的错误。与动规无关），并且由于对动规的不熟悉。心里对其也有一点点的恐惧。可是认定这一道动规并不难，有时自己独立杰出的第一道动规题目。十分想要独立将其AC。然后一直找细节測数据。最终是找到了几处非常不应该犯的细节处理上的错误。这一点让我非常伤心。但最终的AC胜过千言万语。
之后选择还有一种方法，也是磕磕绊绊才写出AC代码orz...
这就算是开了动规吧，多思考多钻研，多学习别人的优秀思路