首页 > 代码库 > TYVJ1199
TYVJ1199
这题切了,顿时感觉很爽,这题彻底摆脱别人的思路和代码,完全是自己想自己写的,本来以为可能会超时,但是想不到别的方法就想把自己的思路写出来验证一下对不对,后来经过无数次的修改调试,最后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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。