分析:暴力角度看,因为数组a和b总和一样,所以实际上是将总和m划分为n个数字,且每个数字都和a数组不一样的方案数。当然会超时。从数据角度看,平方级别算法是可以的。
其实用动态规划的四步法分析起来还是很简单的,我们要构造一个b数组,n个元素,总和是m。哪么按DP思路,先构造一个n-1的数组,总和是m-b[n]。只要b[n]!=a[n]的方案数都是可行的。
因此DP方程很容易得到,dp[i][j]表示构造一个i个数据元素,总和是j的数组。
哪么dp[i][j]=dp[i-1][[j-1]+dp[i1][j-2]+..........
dp[i-1][[j-1]表示我们第i个元素选了1,所以还有j-1的总和给前i-1个元素。当然和a[i]相同的那个排除掉即可。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,a[500],dp[305][505],mod=1e9+7,m;/**< 长整型不是必须,但不容易出错 */
int main()
{
int i,j,k;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i],m+=a[i];
dp[0][0]=1;/**< 你懂的,没这句全是0了 */
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{/**< dp[i][j],前i个数总和是j,且满足条件的方案数量 */
for(k=1;k<=j;k++)/**< k是b[i],也就是序列最后一个数字,前i-1个的方案就是dp[i-1][j-k] */
if(k!=a[i])
dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
}
}
cout<<dp[n][m];
return 0;
}