题解 P1846 【游戏】

stansxt · 2020-05-24 15:40:01 · 题解

前言

• 感觉其它大佬的题解都不是很友善呢~

• 所以这里我主要讲下dp的设计和转移，然后附上窝的代码QwQ

思路

• 一眼dp。
• s代表的是所有数的和，k是个数。所以让每个数都减一，然后求和就直接是s-k了。
• 从前面删和从后面删是没有本质区别的，因为最终要求删完。
• 注意到如果两个数列同时删超过1个数，比如a中a_i,a_j，设删掉的b中元素的和为b_{sum}，那么对答案的贡献就是(a_i+a_j)\times b_{sum}，它与a_i\times b_{sum}+a_j\times b_{sum}是相等的。所以每次至多有一个数列删去超过一个数。
• 看上去是个类似匹配dp的东西。所以设计dp[i][j]表示a数列删去i个数，b数列删去j个数，此时答案的最小值。
• 对于dp[i][j]，那么有三种情况：
  • a$数列仅删去$a_i$，b数列仅删去$b_j$，那么就是$dp[i-1][j-1]+a[i]\times b[j]
  • 同理，还有一个是dp[i-1][j]+a[i]\times b[j]。
• 然后就完啦，O(n^2)直接转移即可。

代码

//P1846 游戏
//submit 1
//By sxt on 2020.5.23
#include<bits/stdc++.h>

#define rg register int
#define il inline
#define in read()
#define _num(x) (x >= '0' && x <= '9')
#define ql(x) memset(x, 0, sizeof(x)) 
#define mid (l+r>>1)
#define min(x, y) (x<y?x:y)
#define Min(x, y, z) min(x, min(y, z))

using namespace std;

const int N = 2007; 

il int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!_num(ch)){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(_num(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

char f[10];
int pcnt;

il void pint(int x){
    pcnt = 0;
    if(x == 0) putchar('0');
    while(x){
        f[++pcnt] = x % 10 + '0';
        x /= 10;
    }
    while(pcnt) putchar(f[pcnt--]);
    putchar('\n');
}

int b[N], a[N], dp[N][N], n, m;

signed main()
{
    n = in, m = in;
    for(rg i = 1; i <= n; ++ i)a[i] = in, --a[i];
    for(rg i = 1; i <= m; ++ i)b[i] = in, --b[i];
    memset(dp, 0x3f3f3f, sizeof(dp));
    dp[0][0] = 0;
    for(rg i = 1; i <= n; ++ i)for(rg j = 1; j <= m; ++ j)
        dp[i][j] = Min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + a[i] * b[j];
    pint(dp[n][m]);
    return 0;
}

The · End.