Tak and Cards(动态规划)

这题是抄LK的。博客就放在这了：

https://blog.csdn.net/m0_37109329/article/details/80381556

大家可以去看看;

题意：

给你N,K，a[1~N].让你要选1～n张牌，且它的平均值是要==k。

dp[i][j][k],i代表到第几个数，j代表次数，k代表数值，代表到第i个数时数值k的出现j次的方式有多少种；

LK代码：、

#include <iostream>
#include <string.h>
#include <algorithm>
#define STD std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
long long dp[55][55][2550];
long long x[50];
int main()
{
    STD;
    int n,v;
    cin>>n>>v;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for (int i=0;i<n;i++)
    {
        cin>>x[i];
        for (int j=0;j<=n;j++)
            for (int k=0;k<=2510;k++)
            {
                if (k>=x[i]&&j>=1)
                    dp[i+1][j][k]=dp[i][j-1][k-x[i]]+dp[i][j][k];
                else
                    dp[i+1][j][k]=dp[i][j][k];
            }   
    }
    long long ans=0;
    for (int i=1;i<=n;i++)
        ans+=dp[n][i][i*v];
    cout<<ans<<endl;
    return 0;
} 

杨哥哥在比赛中途就过来挑衅了（搞事情。）

说了一句二维dp没有没有然后了，。我就在想，一直在思考，一直在寻找。

后来就想不出来了。

后来我才想到它是怎么一回事。

它是用的是dp[i][k]-----i是综合了物品和物品的个数。所以得到二维，看来自己要好好学习dp了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[55][13050]={0};
int main()
{
    ll n,k,a[105];
    memset(dp,0,sizeof(dp));

    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }

    dp[0][0]=1;
    ll tot=0;
    for(int i=1;i<=n;i++){
        tot+=a[i];
        for(int j=i;j>=1;j--){
            for(int K=tot;K>=a[i];K--){
                dp[j][K]+=dp[j-1][K-a[i]];
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[i][i*k];
    }
    printf("%lld\n",ans);
    return 0;
}