首页 > 代码库 > TYVJ1199

TYVJ1199

2024-07-19 06:39:16   222人阅读

这题切了，顿时感觉很爽，这题彻底摆脱别人的思路和代码，完全是自己想自己写的，本来以为可能会超时，但是想不到别的方法就想把自己的思路写出来验证一下对不对，后来经过无数次的修改调试，最后A了，当时就算是返回TLE也不会感觉有什么，没想到竟然A了，oh yeah~
这题还是验证性的dp
dp[0][i][j]表示前i种能否表示j
dp[1][i][j]表示前i种表示j需要的最小邮票张数
最后目标值dp[0][m][j]
(mmax表示能表示的最大的值)
这一题比积木城堡那题多了两个很恶心的条件，最多n张，每种
有无限张
枚举第i种邮票
枚举每种邮票的使用次数j(j<=n &&j*a[i]<=mmax)
枚举k：从j*a[i]->mmax
如果前i-1种能表示k-j*a[i]并且其所使用的最小张数+j<=n
{
更新dp[0][i][k] = dp[0][i][k-j*a[i]] = 1;
更新dp[1][i][k] = min(dp[1][i][k],dp[0][i-1][k-j*a[i]]+j);
更新dp[1][i][k-j*a[i]] = min(dp[1][i][k-j*a[i]],dp[1][i-1][k-j*a[i]]);
}
最后枚举0->mmax
当dp[0][m][i]=false 时
i-1就是answer

 

 

#include<cstdio>#include <cstring>#include <iostream>#include <algorithm>#define INF 11111111using namespace std;const int maxv = 25600;const int maxn = 105;int dp[2][maxn][maxv],a[maxn];int main(){   // freopen("in.txt","r",stdin);    int n,m;    cin>>n>>m;    int mmax = -1;    for(int i = 1;i<=m;++i)    {        scanf("%d",&a[i]);        mmax = max(mmax,a[i]);    }    mmax*=n;    sort(a+1,a+1+m);    memset(dp,0,sizeof(dp));    for(int i = 0;i<=m;++i)        dp[0][i][0] = 1;    for(int i = 1;i<=m;++i)        for(int j = 1;j<=mmax;++j)            dp[1][i][j] = INF;    for(int i = 1;i<=m;++i)        for(int j = 1;j<=n && j*a[i]<=mmax;j++)        {            for(int k = mmax;k>=j*a[i];--k)            {                if(dp[0][i-1][k-j*a[i]] && dp[1][i-1][k-j*a[i]]+j<=n)                {                    dp[0][i][k] = dp[0][i][k-j*a[i]] = 1;                    dp[1][i][k] = min(dp[1][i][k],dp[1][i-1][k-j*a[i]]+j);                    dp[1][i][k-j*a[i]] = min(dp[1][i][k-j*a[i]],dp[1][i-1][k-j*a[i]]);                }            }        }//        for(int i = 0;i<=mmax;++i)//            printf("%d==%d  %d\n",i,dp[0][m][i],dp[1][m][i]);    int ans;    for(int i = 0;i<=mmax;++i)        if(!dp[0][m][i]){ans = i;break;}    ans--;    printf("%d\n",ans);    return 0;}

 

TYVJ1199


联系
我们