Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: QMAX (VNOI) : Tìm đường đi có tổng lớn nhất trong ma trận

  1. #1
    Ngày gia nhập
    05 2011
    Nơi ở
    Hà Nội
    Bài viết
    13

    Mặc định QBMAX (VNOI) : Tìm đường đi có tổng lớn nhất trong ma trận

    Mọi người có hứng thú với mấy bài bên VNOI không nhỉ ???
    Thử bàn bạc bài này xem sao nhé.
    PHP Code:
    1. Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100).
    2. Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
    3.  
    4. Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)
    5. Input
    6.  
    7. Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
    8.  
    9. M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
    10. Output
    11.  
    12. Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được
    13. Example
    14.  
    15. Input:
    16. 5 7
    17. 9 -2 6 2 1 3 4
    18. 0 -1 6 7 1 3 3
    19. 8 -2 8 2 5 3 2
    20. 1 -1 6 2 1 6 1
    21. 7 -2 6 2 1 3 7
    22.  
    23. Output:
    24. 41
    Đã được chỉnh sửa lần cuối bởi phuongham : 07-07-2011 lúc 04:39 AM. Lý do: Sửa tên bài viết

  2. #2
    Ngày gia nhập
    07 2010
    Nơi ở
    Thư viện
    Bài viết
    123

    mình làm được 2 cách :
    cách 1: quét cạn.
    cách 2:dùng quy hoạnh động.
    "một người chưa bao giờ vấp ngã, chưa bao giờ thất bại, chưa bao giờ phạm phải bất kỳ một sai lầm nào là một người có tương lai vô cùng mờ mịt." - Og Mandino

    Tổng hợp các quyển sách hay Mp3

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    6

    m nghĩ bài này có thể dùng thuật toán tham lam.

  4. #4
    Ngày gia nhập
    05 2011
    Nơi ở
    ~
    Bài viết
    20

    Trích dẫn Nguyên bản được gửi bởi phuongham Xem bài viết
    Mọi người có hứng thú với mấy bài bên VNOI không nhỉ ???
    Thử bàn bạc bài này xem sao nhé.
    PHP Code:
    1. Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100).
    2. Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
    3.  
    4. Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)
    5. Input
    6.  
    7. Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
    8.  
    9. M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
    10. Output
    11.  
    12. Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được
    13. Example
    14.  
    15. Input:
    16. 5 7
    17. 9 -2 6 2 1 3 4
    18. 0 -1 6 7 1 3 3
    19. 8 -2 8 2 5 3 2
    20. 1 -1 6 2 1 6 1
    21. 7 -2 6 2 1 3 7
    22.  
    23. Output:
    24. 41
    Giải bằng qui hoạch động. Theo giả thiết thì có 3 cách để tới được ô (i, j) trong một bước: từ (i, j-1), (i-1, j-1), hoặc (i+1, j-1). Đặt s(i, j) là tổng lớn nhất để tới ô (i, j), thì s(i, j) = max{s(i, j-1), s(i-1, j-1), s(i+1, j-1)} + a(i, j).

    Tạo một bảng kích thước m x n. Cột thứ nhất được khởi tạo giá trị như cột thứ nhất của ma trận đầu vào. Tính dần các giá trị cho các cột tiếp theo dựa trên công thức ở trên. Sau đó, tìm giá trị lớn nhất ở cột cuối cùng.

    Trong ví dụ ở trên, đường đi tối ưu là: 9, -1, 8, 7, 5, 6, 7 (tổng là 41).
    if (x >> 0) // if x is much larger than 0?

  5. #5
    Ngày gia nhập
    05 2011
    Nơi ở
    Hà Nội
    Bài viết
    13

    Hi Hôm qua tớ làm được bài này rồi ))
    Cách của tớ sử dụng qui hoạch động.
    Chỉ có nếu ta để nguyên mảng như vậy thì sẽ phải xét đến các trường hợp phần tử nằm trên biên. Do đó tớ lưu mảng trên vào mảng (m + 2) * n. Trong đó hàng đầu và hàng cuối tất cả các số bằng INT_MIN. m hàng ở giữa là mảng đã cho. Rồi duyệt mảng như các bạn miêu tả.

  6. #6
    Ngày gia nhập
    04 2012
    Bài viết
    3

    Mặc định Nhờ giúp đỡ

    Bạn nào rãnh giải dùm đề bài "tìm đường đi lớn nhất" dùm mình với, mình đang cần gấp.
    Thanks

  7. #7
    Ngày gia nhập
    07 2009
    Nơi ở
    Thị trấn Lâm Thao - Phú Thọ
    Bài viết
    86

    Code:
    #include <stdio.h>
    #include <string.h>
    void nhap(void);
    void xuly(void);
    void xuat(void);
    int m,n;
    char a[102][102];
    int kq;
    int main(void)
      {
        nhap();
        xuly();
        xuat();
        return 0;  
      }
    void nhap(void)
      {
        scanf("%i%i",&m,&n);
        int i,j;
        for(i=1;i<=m;++i)
          for(j=1;j<=n;++j)
            scanf("%i",&a[i][j]);
      }
    void xuly(void)
      {
        int i,j;
        int max;
        
        int b[102][102];
        memset(b,0,sizeof(b));
        for(i=1;i<=m;++i)
          {
            b[i][n]=a[i][n];
          }
        
        
        for(j=n-1;j>0;--j)
          {
            
            for(i=1;i<=m;++i)
              {
                if(i==1)
                  {
                    if(b[i][j+1]<b[i+1][j+1])
                      b[i][j]=a[i][j]+b[i+1][j+1];
                    else
                      b[i][j]=a[i][j]+b[i][j+1];
                  }
                else if(i==m)
                  {
                    if(b[i][j+1]<b[i-1][j+1])
                      b[i][j]=a[i][j]+b[i-1][j+1];
                    else
                      b[i][j]=a[i][j]+b[i][j+1];
                  }
                else
                  {
                    max=b[i-1][j+1];
                    if(max<b[i][j+1])
                      max=b[i][j+1];
                    if(max<b[i+1][j+1])
                      max=b[i+1][j+1];
                    b[i][j]=a[i][j]+max;
                  }
              }
          }
        
        max=b[1][1];
        for(i=2;i<=m;++i)
          if(max<b[i][1])
            max=b[i][1];
        kq=max;  
      }
    void xuat(void)
      {
        printf("%i",kq);
      }
    Ngô Hùng Cường
    Birthday: 14/4/1986 - Cư ngụ: Thị trấn Lâm Thao - Phú Thọ
    kidteam@gmail.com
    Yahoo ID: cuong_dhbk2004
    0989696971
    0915696971

  8. #8
    Ngày gia nhập
    07 2011
    Bài viết
    2

    các anh xem giúp em với, trên pc em đã test rất nhiều trường hợp, không thấy sai,nhưng đăng code lên spoj.pl thì lại báo sai.
    Code:
    #include <iostream>
    #include <fstream>
    #define MAX 500
    using namespace std;
    ifstream fin("IN.txt");
    ofstream fout("OUT.txt");
    void Nhap(long long int a[][MAX],int n,int m)
    {
       for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
             fin>>a[i][j];
    }
    int Max(int a,int b,int c)
    {
       int max=a;
       if(b>max) max=b;
       if(c>max) max=c;
       return max;
    }
    void XuLy(long long int a[][MAX],int n,int m)
    {
       for(int j=2;j<=m;j++)
          for(int i=1;i<=n;i++)
             a[i][j]=a[i][j]+Max(a[i-1][j-1],a[i][j-1],a[i+1][j-1]);
       for(int i=1;i<n;i++)
          for(int j=i+1;j<=n;j++)
             if(a[i][m]>a[j][m])
             {
                long long int t=a[i][m];a[i][m]=a[j][m];a[j][m]=t;
             }
       fout<<a[n][m];
    }
    int main()
    {
       long long int a[MAX][MAX];
       int n,m;
       fin>>n>>m;
       Nhap(a,n,m);
       XuLy(a,n,m);
       return 0;
    }

  9. #9
    Ngày gia nhập
    12 2010
    Nơi ở
    Cần thơ
    Bài viết
    273

    Code của mình , bạn tham khảo
    C Code:
    1. /* Trân Vu Lâm */
    2. /*             */
    3. /* QBMAX       */
    4. #include <algorithm>
    5. #include <stdio.h>
    6. #include <stdlib.h>
    7.  
    8. #define INF 1071071071
    9. #define maxN 105
    10.  
    11. using namespace std;
    12.  
    13. int r,c;
    14. int data[maxN][maxN];
    15. int ans[maxN][maxN];
    16.  
    17. int nx[] = {-1,0,1};
    18. int ny[] = {-1,-1,-1};
    19.  
    20. int main()
    21. {
    22.        
    23.     scanf("%d %d",&r,&c);
    24.     for (int i = 0 ; i < r ; i++)
    25.         for (int j = 0 ; j < c ; j++)
    26.             scanf("%d",&data[i][j]);
    27.            
    28.    
    29.     for (int i = 0 ; i < r ; i++)
    30.         ans[i][0] = data[i][0];
    31.        
    32.     for (int j = 1 ; j < c ; j++)
    33.         for (int i = 0 ; i < r ; i++)
    34.         {
    35.             ans[i][j] = -INF;
    36.             for (int k = 0 ; k < 3 ; k++)
    37.             {
    38.                 int x = i + nx[k] , y = j + ny[k];
    39.                 if (x >= 0 && x < r)
    40.                     ans[i][j] = max(ans[i][j], data[i][j] + ans[x][y]);
    41.             }
    42.         }
    43.    
    44.     int mans = -INF;
    45.     for (int i = 0 ; i < r ; i++)
    46.         mans = max(mans,ans[i][c - 1]);
    47.        
    48.     printf("%d\n",mans);
    49.        
    50.  
    51.     return 0;
    52. }

    Trích dẫn Nguyên bản được gửi bởi loctinh2030 Xem bài viết
    các anh xem giúp em với, trên pc em đã test rất nhiều trường hợp, không thấy sai,nhưng đăng code lên spoj.pl thì lại báo sai.
    Code:
    ...
             a[i][j]=a[i][j]+Max(a[i-1][j-1],a[i][j-1],a[i+1][j-1]);
    ...
    bác có xét là i - 1 là 0 hoặc i + 1 > n -> truy xuất ngoài mảng hok
    Ai bất tài, tôi nhìn hoài chẳng thấy,
    Đi khắp phòng tôi lấy 1 tấm gương,
    Khẽ đặt lên một góc phía bức tường,
    Nhìn vào đó, tôi tận tường kẻ đó.

Các đề tài tương tự

  1. Cấp phát động bộ nhớ gặp lỗi không nhập được giá trị cho ma trận trong C++.
    Gửi bởi hidden trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 24
    Bài viết cuối: 25-11-2011, 03:27 AM
  2. Bài toán Nước đọng trên VNOI viết bằng C. Chạy không đúng...
    Gửi bởi minhtuan.a0 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 5
    Bài viết cuối: 22-11-2011, 01:42 PM
  3. Bài toán Phân tích số ( Bài KTUAN - VNOI )
    Gửi bởi pannaruto trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 14-07-2011, 10:35 PM
  4. Bài tập C Về cách nhập và sửa một ma trận trong lập trình?
    Gửi bởi tictic trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 09-11-2010, 12:11 AM
  5. Tìm hàng có tổng nhỏ nhất trong ma trận
    Gửi bởi anhtuan90 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 22-04-2010, 10:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn