题号：1508
感动哭，第一个自己不用想状态转移方程就写出来的动规超级简单题……我是有多辣鸡……
这样的题一天做20道都没问题啊，要是NOIP全考这个就好了（逃）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include<iostream> #include<algorithm> #include<string> #include<utility> #include<queue> #include<cstdlib> #include<cstring> #include<map> using namespace std; int n, m; int f[205][205],arr[205][205]; int main(){ ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cin >> arr[i][j]; } } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ f[i][j] = max(max(f[i - 1][j], f[i - 1][j - 1]), f[i - 1][j + 1]) + arr[i][j]; } } cout << max(max(f[n][m / 2 + 1],f[n][m/2]),f[n][m/2+2]); } |
20180802更新：
呃呃呃。。。。因为之前做过这样的题所以才觉得很简单。。。。。。。。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include<iostream> #include<string> #include<cstring> #include<algorithm> using namespace std; int m, n; int arr[205][205]; int main() { memset(arr, 0x80, sizeof(arr)); cin >> m >> n; for (int i = 1; i <= n; i++)arr[0][i] = 0; arr[m+1][(n + 1) / 2] = 0; for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j]; for (int i = m; i >= 0; i--) { for (int j = 1; j <= n; j++) { arr[i][j] += max(max(arr[i + 1][j - 1], arr[i + 1][j]), arr[i + 1][j + 1]); } } int mmax = 0; for (int i = 1; i <= n; i++) { mmax = max(mmax, arr[0][i]); } cout << mmax; } |