PAT (Advanced Level) 1068. Find More Coins (30)

01背包路径输出。

保证字典序最小:从大到小做背包。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>
using namespace std; const int maxn=+;
bool dp[maxn*maxn][maxn];
int a[maxn*maxn];
int n,k;
vector<int>ans;
struct Path
{
int r,c;
}p[maxn*maxn][maxn]; bool cmp(const int &a,const int &b)
{
return a>b;
} int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a++n,cmp);
memset(dp,,sizeof dp);
for(int i=;i<=n;i++)
for(int j=;j<=k;j++)
p[i][j].r=p[i][j].c=-;
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=k;j++)
{
if(dp[i-][j]==) continue;
if(j+a[i]>k) continue;
dp[i][j+a[i]]=;
p[i][j+a[i]].r=i-;
p[i][j+a[i]].c =j;
}
for(int j=;j<=k;j++)
{
if(dp[i-][j]==&&dp[i][j]==)
{
p[i][j].r=p[i-][j].r;
p[i][j].c=p[i-][j].c;
}
dp[i][j]=max(dp[i][j],dp[i-][j]);
}
} if(dp[n][k]==) printf("No Solution\n");
else
{
int nowr=n,nowc=k;
while()
{
ans.push_back(nowc-p[nowr][nowc].c);
int tmpr=nowr,tmpc=nowc;
nowc=p[tmpr][tmpc].c;
nowr=p[tmpr][tmpc].r;
if(nowc==) break;
}
for(int i=;i<ans.size();i++)
{
printf("%d",ans[i]);
if(i<ans.size()-) printf(" ");
else printf("\n");
}
}
return ;
}
上一篇:vi/vim使用进阶: 剑不离手 – quickfix


下一篇:Thinkphp框架下设置session的过期时间