背包判断能否用n个数之和表示某个数

内容概述

本篇有两题
第二题为第一题的进阶,个人感觉题很不错

1.题目传送门

大致思路

选取100个数组内的数 k ($1≦k≦10$) 可以明确的是n足够大(可选够多)时肯定可以选出来,接下来讨论怎么解决 n 比较小的时候

我们可以用一个桶记录这些数出现的次数 cnt
十的倍数我们可以转化为 末位数字为 0 的数字 ,那么怎么转化为背包问题?
选100个数(容量) ,这些数字的末位数字就为价值
记dp[s][r],s为当前选了多少数,r表示能取到的末位数字.
遍历每一个数字(1-10) 对应末位数字为 0-9 ,做一个背包问题

$$dp[s+t][newr]=dp[s][oldr] $$

newr为oldr加上选择的t个数字得到的末位数字,注意要倒序遍历,否则会出现重复利用的操作

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Mio_qh signed
#define el '\n'
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pq priority_queue
const int MOD = 998244353;
const int N = 100721;


void solve() {
	int n;
	cin >> n;
	vector<int> cnt(10);
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		cnt[x % 10]++; //取末位数字
	}
	if (n>=1000) {
		cout << "YES" << el;
		return;
	}
	vector<vector<bool>> dp(107, vector<bool>(21, false));
	dp[0][0] = true; //初始化,0张牌0总和肯定是可以的
	for (int i = 0; i <= 9; i++) {
		int count = cnt[i];
		if (!count) continue;
		vector<vector<bool>> newdp = dp; //同样是为了避免重复利用
		for (int j = 100; j >=0 ; j--) {
			for (int r=0;r<=9;r++) {
				if (!dp[j][r]) continue;
				for (int k=1;j+k<=100 && k<=count;k++ ) {
					int newr=(r+(k*i))%10;
					newdp[j+k][newr] = true;
				}
			}
		}
		dp=newdp; //更新dp数组
	}
	if (dp[100][0]) cout << "YES" << el;
	else cout << "NO" << el;
}


Mio_qh main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	// cin >> tt;
	while (tt--) solve();
}

2.题目传送门

大概算是上一题的进阶题

大致思路

首先观察数据范围 $(1≦n≦100)$ 和 $(1≦a_i≦200)$ 可以想到枚举出部分范围的有趣数,可以写一个程序来枚举1-20000的所有有趣数

为什么是 1-20000 ? 想一想这个数据范围能组成的最大总和是多少? $20000$ !

为什么说这题是上一题的进阶题,因为很明显, 1 是一个有趣数,无论怎么样,我们都可以将数组中的n-1个元素变为1,剩下一个元素承担剩下的总和.(也是因为这一点,打上了思维tag)
那什么情况下答案可以是 n ? 就是这 n 个数的总和与由 n 个有趣数构成的总和相等的时候
此时可以转化为上一题的背包问题
记dp[i][j],i为选了多少数,j为当前总和,有下面状态转移方程

$$dp[i][j]=dp[i-1][j-x] $$

其中x为有趣数,因为这里任一有趣数的数量是"无限"的,所以不用考虑重复利用问题.
补充:考虑预处理

Code

Assistance

int getDigit(int x) {
    if(x==0) return 0;
    int res=0;
    while(x!=0) {
        res+=x%10;
        x/=10;
    }
    return res;
}
bool isVaild(int x) {
    int t=sqrt(x);
    if(t*t==x) return true;
    return false;
}

void solve() {
    for (int i=1;i<=20000;i++) {
        if(!isVaild(i)) continue;
        int digit=getDigit(i);
        if (isVaild(digit)) printf("%d,",i);
    }
}

Solution

 #include <bits/stdc++.h>
using namespace std;
#define int long long
#define Mio_qh signed
#define el '\n'
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pq priority_queue
constexpr int MOD = 998244353;
constexpr int N = 100721;
int bzd[]={1,4,9,36,81,100,121,144,169,196,225,324,400,441,484,529,900,961,1521,1681,2025,2304,2601,3364,3481,3600,4489,4624,5776,5929,7225,7396,8100,8836,9025,10000,10201,10404,10609,10816,11025,12100,12321,12544,12769,14400,14641,14884,16900,17161,19321,19600}; //1-20000内的有趣数

vector<vector<bool>> dp(101,vector<bool>(20001,false));

void solve() {
    int n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        sum+=x;
    }
    if (n==1) { //特判
        for(auto x:bzd) {
            if (sum==x) {
                cout<<1<<endl;
                return;
            }
        }
        cout<<0<<endl;
    }
    else {
        if (dp[n][sum]) cout<<n<<endl; //n个有趣数能否使得总和为sun
        else cout<<n-1<<endl;
    }

}

Mio_qh main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    dp[0][0] = true;
    for(int i=1;i<=100;i++) {
        for(int j=1;j<=20000;j++) {
            for (auto x:bzd) { //枚举每个有趣数作为总和的组成
                if (j >= x && dp[i-1][j-x]) {
                    dp[i][j] = true;
                    break;
                }
            }
        }
    }
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
}