小__同 小__同
关注数: 2 粉丝数: 0 发帖数: 25 关注贴吧数: 15
求助,hdoj1024 动态规划 不知道错在哪里,自己试了几个,感觉结果没什么问题,但无法通过。 帮看看问题出在哪里。谢谢代码如下: #include <iostream> #include <string> using std::cin; using std::cout; using std::endl; int sum(int begin, int end, int m, int**data) { if (begin== end){ //cout << '(' << begin << ',' << end << ')' << data[begin][end] << " "; return data[begin][end]; } int max; if (m == 1){ max = data[begin][begin]; for (int i = begin; i <= end; i++){ for (int j = i ; j <= end; j++){ int newdata = data[i][j]; if (newdata > max){ max = newdata; } } } //cout << '(' << begin << ',' << end << ')' << max << " "; return max; } max = data[begin][begin] + sum(begin + 1, end, m - 1, data); for (int i = 1; i < end - begin - m + 2; i++){ int newdata = sum(begin, begin + i, 1, data) + sum(begin + i + 1, end, m - 1, data); if (newdata > max){ max = newdata; } } //cout << '(' << begin << ',' << end << ')' << max << " "; return max; } int main(){ int num, m; while (true){ cin >> m >> num; int * data = new int[num]; for (int i = 0; i < num; i++){ cin >> data[i]; } int * data1 = new int[num * (num+1)/2]; int ** data2 = new int *[num]; for (int i = 0, s = 0; i < num; i++){ s += i; data2[i] = &data1[num * i - s]; } //建立二维数组 for (int i = 0; i < num; i++){ data2[i][i] = data[i]; for (int j = i+1; j < num; j++){ data2[i][j] = data2[i][j - 1] + data[j]; } } cout/* << endl */<< sum(0, num - 1, m, data2) << endl; delete[]data; delete[]data1; delete[]data2; } system("pause"); return 0; }
求助,hdoj1024 动态规划 不知道错在哪里,自己试了几个,感觉结果没什么问题,但无法通过。 帮看看问题出在哪里。谢谢代码如下: #include <iostream> #include <string> using std::cin; using std::cout; using std::endl; int sum(int begin, int end, int m, int**data) { if (begin== end){ //cout << '(' << begin << ',' << end << ')' << data[begin][end] << " "; return data[begin][end]; } int max; if (m == 1){ max = data[begin][begin]; for (int i = begin; i <= end; i++){ for (int j = i ; j <= end; j++){ int newdata = data[i][j]; if (newdata > max){ max = newdata; } } } //cout << '(' << begin << ',' << end << ')' << max << " "; return max; } max = data[begin][begin] + sum(begin + 1, end, m - 1, data); for (int i = 1; i < end - begin - m + 2; i++){ int newdata = sum(begin, begin + i, 1, data) + sum(begin + i + 1, end, m - 1, data); if (newdata > max){ max = newdata; } } //cout << '(' << begin << ',' << end << ')' << max << " "; return max; } int main(){ int num, m; while (true){ cin >> m >> num; int * data = new int[num]; for (int i = 0; i < num; i++){ cin >> data[i]; } int * data1 = new int[num * (num+1)/2]; int ** data2 = new int *[num]; for (int i = 0, s = 0; i < num; i++){ s += i; data2[i] = &data1[num * i - s]; } //建立二维数组 for (int i = 0; i < num; i++){ data2[i][i] = data[i]; for (int j = i+1; j < num; j++){ data2[i][j] = data2[i][j - 1] + data[j]; } } cout/* << endl */<< sum(0, num - 1, m, data2) << endl; delete[]data; delete[]data1; delete[]data2; } system("pause"); return 0; }
1 下一页