JumpingMachine(集合选数问题)xiaodangao

Jumping Machine
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 megabytes
Young inventor has created a new jumping machine. In order to test it, he brought it to the testing polygon. The polygon is an infinite square grid.
Initially, the machine is located in the cell (0, 0). The machine has n springs, the i-th spring has the force of li and allows the machine to jump li cells up or li cells to the right. Therefore this spring allows the machine to get from cell (x, y) either to cell (x + li, y), or to cell (x, y + li). After jumping, the spring is thrown back and cannot be reused. The machine can use the springs in any order.
During the tests the cells, that the machine will fly over, will be stained with machine oil. In order not to clean the grid after himself, the inventor has decided to put a protective mat on each cell the machine could potentially fly over. Now the inventor is wondering how many protective mats he needs to bring to the test with him.
Input
The first line of input contains n — the number of springs that the machine has (1 ≤ n ≤ 100). The second line contains n integers li — the springs forces (li ≥ 1; 1 ≤ l1 + l2 + · · · + ln ≤ 106).
Output
Output a single integer: the number of mats that inventor needs to bring.
Example
standard input standard output
2
4 2
22
Explanation
All the cells that can get dirty when the machine jumps in the example test are colored orange one the figure below

思路：感觉有点像 $dp$ ，首先发现所有终点 $(x,y),x+y$ 为定值，然后发现我们可以定一个 $x$ 增加的长度，当然这个长度是属于 $arr_i$ 的，那么 $y$ 增加的长度就是 $sum-x$ ，然后我们不用考虑先上移再右移再上移这种情况，我们只需要枚举出 $x$ 增加的长度，即可，这么做显然是正确的，因为我们枚举了所有可能到达的 $x$ 长度，相应的 $y$ 的长度也已经完全了，然后分别做出先延 $x$ 走到头，再延 $y$ 走到头，和先延 $y$ 走到头，再延 $x$ 走到头，可以发现构成一个矩形，随着 $x$ 枚举长度的增加，会与矩形一条边有 $tot-2$ 个交点，复杂情况只会走到格点上；最后是求所有 $x$ 可能长度的方法，该方法设 $0$ 时刻的集合里只有一个 $0$ 元素，该方法的本质是完成了从 $i-i+1$ 的过渡，就是如果我们在已完备的前 $i$ 个数中增加一个数，增加的这下标为 $i+1$ 的值对集合所做的贡献，很明显是前 $i$ 个数所构成的所有值 $+arr_i+1$ ，再进行一步去重操作，得到的就是方案数，并且范围 $1e6$ 不会超时的；
这个题思考的时间太长了，是不应该的，发现题目范围的端倪之后，应该想到该方法来解，感觉这个方法以前用过。如果直接思考的话最简单的就是枚举这样的话答案是一共有 $2^n$ 方种，接受不了。
$code：$


/*************************************************************************
    > File Name: problemA.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年12月16日 星期三 15时34分48秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e3+10,maxn = 1e6+10;
ll n;ll arr[N],sum = 0;
bool st[maxn];ll b[maxn];
void solve(){
    scanf("%lld",&n);
    ll ans = 0,now = 1;
    for(ll i=1;i<=n;++i){
        scanf("%lld",&arr[i]);
        sum += arr[i];
    }
    ll tot = 0;
    b[++tot] = 0;
    st[0] = true;
    for(ll i=1;i<=n;++i){
        ll k = tot;
        for(ll j=1;j<=k;++j){
            ll p = b[j] + arr[i];
            if(st[p] == true)continue;
            b[++tot] = p;
            st[p] = true;
        }
    }
    //printf("%lld\n",tot);
    now = tot-3;
    ans-=(now*(now+1))/2;
    now++;
    //printf("%lld\n",now);
    //printf("%lld %lld\n",ans,now);
    ans+=now * (sum-1);
    ans+=2*sum;
    printf("%lld\n",ans+1);
}
int main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。