命運

穿過幽谷意味著離大魔王lemon已經無限接近了！
可誰能想到，yifenfei在斬殺了一些蝦兵蟹將后，卻再次面臨命運大迷宮的考驗，這是魔王lemon設下的又一個機關。要知道，不論何人，若在迷宮中被困1小時以上，則必死無疑！
可憐的yifenfei為了去救MM，義無返顧地跳進了迷宮。讓我們一起幫幫執著的他吧！
命運大迷宮可以看成是一個兩維的方格陣列，如下圖所示：

yifenfei一開始在左上角，目的當然是到達右下角的大魔王所在地。迷宮的每一個格子都受到幸運女神眷戀或者痛苦魔王的詛咒，所以每個格子都對應一個值，走到那里便自動得到了對應的值。
現在規定yifenfei只能向右或者向下走，向下一次只能走一格。但是如果向右走，則每次可以走一格或者走到該行的列數是當前所在列數倍數的格子，即：如果當前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。
為了能夠最大把握的消滅魔王lemon，yifenfei希望能夠在這個命運大迷宮中得到最大的幸運值。

      

        
   
   1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
  
  
      
    

      

        
   
   52
  
  
      
    

狀態轉移方程：

sum[i][j] = max{sum[i - 1 ][j],sum[i][k]} + v[i][j];其中1 <= k <= j - 1 ,且k是j的因子

上面的要用二維數組。

其實完全可以優化為一維數組。這里用 opt[j] = max{ opt[j], {opt[k]} } + map[i][j] ; 其中1 <= k <= j - 1, 且k是j的因子

另外，第一行要單獨處理。

見代碼：

    #include <iostream>
#include <string.h>
#include <stdlib.h>
#include <fstream>
using namespace std;

int main() {
	//ifstream cin("D:\\C++\\eclipse_work\\動態規劃\\testcpp\\input.txt");

	int k, m, n, temp;
	cin >> k;
	int opt[1002];
	while (k--) {
		memset(opt, 0, sizeof(opt));
		cin >> m >> n;
		cin >> opt[1]; //第一行第一列 沒得選。

		//遍歷第一行. 由于第一行比較特殊，只能從左邊到達，單獨處理。
		for (int j = 2; j <= n; j++) {
			cin >> temp;
			for (int k = 1; k <= j / 2; k++) {
				if (j % k == 0) {
					if (opt[j] ==0 ||   opt[j] < opt[k] + temp)
						opt[j] = opt[k] + temp;
				}
			}
			if ((j > 2 && opt[j] < opt[j - 1] + temp) || opt[j] ==0)
				opt[j] = opt[j - 1] + temp;
		}

		//遍歷后面幾行。 兩種可能   找到一個較大的即可
		for (int i = 1; i < m; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> temp;
				int t = opt[j];
				for (int k = 1; k <= j / 2; k++) {
					if (j % k == 0) {
						if ( opt[k] > t)
							t = opt[k];
					}
				}
				if (j > 2 &&  opt[j - 1] >  t)
					t = opt[j - 1] ;
				opt[j] = t + temp;
			}
		}
		cout << opt[n] << endl;

	}
	return 0;
}
  

動態規劃-HOJ-2571