摘花生
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N], T, n, m, w[N][N];
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &w[i][j]);
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
}
printf("%d\n", f[n][m]);
}
return 0;
}
最低通行费
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N], n, w[N][N];
int main()
{
scanf("%d", &n);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
scanf("%d", &w[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == 1 && j == 1) f[i][j] = w[i][j];
else f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
printf("%d\n", f[n][n]);
return 0;
}
方格取数
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int f[N + N][N][N], n, w[N][N];
int main()
{
scanf("%d", &n);
int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) && a || b) w[a][b] = c;
for (int k = 1; k <= n + n; k ++ )
for (int i1 = 1; i1 <= n; i1 ++ )
for (int i2 = 1; i2 <= n; i2 ++ )
{
int j1 = k - i1, j2 = k - i2;
if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue ;
int &x = f[k][i1][i2];
int t = w[i1][j1];
if (i1 != i2) t += w[i2][j2];
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
}
printf("%d\n", f[n + n][n][n]);
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;
int f[N][N][N], n, w[N][N], m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);
for (int k = 1; k <= n + m; k ++ )
for (int i = 1; i < k; i ++ )
for (int j = 1; j < k; j ++ )
{
int &x = f[k][i][j];
int t = w[i][k - i];
if (i != j) t += w[j][k - j];
x = max(x, f[k - 1][i][j - 1] + t);
x = max(x, f[k - 1][i][j] + t);
x = max(x, f[k - 1][i - 1][j] + t);
x = max(x, f[k - 1][i - 1][j - 1] + t);
}
printf("%d\n", f[n + m][n][n]);
return 0;
}
标签:d%,i1,--,scanf,i2,int,三角形,include,DP
From: https://www.cnblogs.com/StkOvflow/p/17031577.html