题解：P9102 [PA 2020] Cukierki

大致思路

~~根据算法标签，可知这题是一道动态规划。~~

首先定义

dp[i][j]

表示前

i

个数能够表示

[1，j]

这个范围中的所有数字。

由题显然可得：

$dp[i][j]=dp[i-1][j]$ （在不选 $a[i]$ 的情况)
$dp[i][j]=dp[i-1][j-a[i]]$ (在选 $a[i]$ 的情况)

很显然应为均为

i-1

，所以这一维直接滚掉。

我们把数组从小到大排序，根据贪心可知，在

a_i<a_j

时，如果加上

a_i

时，就大于总数，则

a_j

就不用说了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3,mod=1e9+7;
int n,a[maxn+5],f[maxn+5],ans;
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
	}
	sort(a+1,a+n+1);
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=maxn;j>=a[i]-1;j--)
		{
			int now=min(j+a[i],maxn);
			f[now]=(f[now]+f[j])%mod;
		}
	}
	for(int i=1;i<=maxn;i++)
	{
		ans=(ans+f[i])%mod;
	}
	printf("%d",ans);
	return 0;
}

题解：P9102 [PA 2020] Cukierki

文章操作

大致思路

代码

相关推荐

评论

题解：P9102 [PA 2020] Cukierki