本文共 2171 字，大约阅读时间需要 7 分钟。

【SSL】1644取数字问题

Time Limit:1000MS

Memory Limit:65536K

Description

给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。

Input

第一行两个整数M，N，（2<=M,N<=10），分别表示矩阵的行和列的数目。

Output

仅一行一个整数，表示所选道路上数字之和所能达到的最小的正整数。如果不能达到任何正整数就输出-1。

Sample Input

2 2

Sample Output

1

记忆化搜索

思路

用bool数组保存所有的状态。

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int s=50;int n,m,a[110][110];bool f[1010][1010][1010];void input(){ int i,j; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&a[i][j]); } } return;}void DFS(int x,int y,int t){ f[x][y][t+s]=1;//标记为1 if (x==n&&y==m) return; if (x+1<=n&&f[x+1][y][t+a[x+1][y]+s]==0)//判断越界和访问 DFS(x+1,y,t+a[x+1][y]); if (y+1<=m&&f[x][y+1][t+a[x][y+1]+s]==0) DFS(x,y+1,t+a[x][y+1]); return;}void output(){ int i; for(i=s+1;i<=2*s;i++) { if (f[n][m][i]) { printf("%d",i-s); return; } } printf("-1"); return;}int main(){ input(); DFS(1,1,a[1][1]); output(); return 0;}
          
         
        
       
      
     
    
   

动态规划

思路

用bool数组保存所有的状态。

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int s=50;int n,m,a[110][110];bool f[1010][1010][1010];void input(){ int i,j; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&a[i][j]); } } return;}void DP(){ int i,j,k; f[1][1][a[1][1]+s]=1; for(i=2;i<=m;i++) for(j=0;j<=2*s;j++) if (f[1][i-1][j]) f[1][i][j+a[1][i]]=1; for(i=2;i<=n;i++) for(j=0;j<=2*s;j++) if (f[i-1][1][j]) f[i][1][j+a[i][1]]=1; for(i=2;i<=n;i++) { for(j=2;j<=m;j++) { for(k=0;k<=2*s;k++) { if (f[i-1][j][k]) f[i][j][k+a[i][j]]=1;//状态转移方程 if (f[i][j-1][k]) f[i][j][k+a[i][j]]=1; } } } return;}void output(){ int i; for(i=s+1;i<=2*s;i++) { if (f[n][m][i]) { printf("%d",i-s); return; } } printf("-1"); return;}int main(){ input(); DP(); output(); return 0;}