2192번: 두 수열

https://www.acmicpc.net/problem/2192

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, dpa[2001][2001], dpb[2001][2001], a[2001], b[2001];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) scanf("%d", b + i);
    for (int i = 1; i <= n; i++) dpb[i][1] = dpb[i - 1][1] + (a[i] - 1)*(b[1] - 1);
    for (int i = 1; i <= m; i++) dpa[1][i] = dpa[1][i - 1] + (a[1] - 1)*(b[i] - 1);
    for (int i = 2; i <= n; i++) dpa[i][1] = 2e9;
    for (int i = 2; i <= m; i++) dpb[1][i] = 2e9;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            int t = min(dpa[i - 1][j - 1], dpb[i - 1][j - 1]);
            dpa[i][j] = min(t + (a[i] - 1)*(b[j] - 1), dpa[i][j - 1] + (a[i] - 1)*(b[j] - 1));
            dpb[i][j] = min(t + (a[i] - 1)*(b[j] - 1), dpb[i - 1][j] + (a[i] - 1)*(b[j] - 1));
        }
    }
    printf("%d", min(dpa[n][m], dpb[n][m]));
    return 0;
}