\u8fd9\u9053\u9898\u8fd8\u662f\u6709\u70b9\u96be\u7684\u62c9\u3002\u3002\uff08\u6211\u592a\u6c99\u8336\u4e86\u3002\u3002\uff09
\u9996\u5148\u53ef\u4ee5\u770b\u6210\u6709\u4f9d\u8d56\u7684\u80cc\u5305\u95ee\u9898\u3002\u3002
\u628a\u7259\u9f7f\u548c\u7259\u9f88\u90fd\u770b\u6210\u7269\u54c1\u3002\u3002\u7259\u9f7f\u82e5\u8981\u88ab\u9009\u5219\u653e\u4ed6\u7684\u7259\u9f88\u4e5f\u8981\u88ab\u9009\u3002\u3002\u4e0d\u5c31\u662f\u4f9d\u8d56\u4e48\u3002\u3002
\u9996\u5148\u628a\u7269\u54c1\u91cd\u65b0\u6392\u4e00\u4e0b\u4f4d\u7f6e\uff08\u6211\u662f\u7528dfs\u7684\u3002\u3002\u770b\u6210\u6811\u7684\u8bdd\u3002\u3002dfs\u5e8f\u6b63\u597d\u6ee1\u8db3\u8981\u6c42\u4fc4\uff09\u3002\u3002\u628a\u7259\u9f7f\u90fd\u653e\u5728\u5b83\u4f9d\u8d56\u7684\u7259\u9f88\u7684\u540e\u9762\u3002\u3002
\u518d\u5728\u5f00\u5934\u653e\u4e2a\u865a\u62df\u7269\u54c1\u3002\u3002\u65b9\u4fbf\u7f16\u7a0b\u3002\u3002\u3002
\u8fd9\u6837\u4e0d\u9009\u7684\u8bdd\u5c31\u53ef\u4ee5\u5f80\u540e\u8df3\u8fc7\u90a3\u4e9b\u7259\u9f7f\u3002\u3002\u5c31\u53ef\u4ee5DP\u4e86
\u6709\u4e24\u79cd\u505a\u6cd5\u3002\u3002\u4e4b\u95f4\u7684\u5bf9\u6bd4\u8fd8\u662f\u5f88\u6709\u610f\u4e49\u7684\u3002\u3002
1\uff1a\u6c99\u8336\u505a\u6cd5\uff0850\u5206\uff09
\u8bbeDP[pos,have]\u4e3a\u4ece\u7b2cpos\u4e2a\u7269\u54c1\u5f00\u59cb\uff0c\u8fd8\u6709have\u7684money\u6700\u591a\u80fd\u9009\u51e0\u4e2a\u3002\u3002
\u5219pos\u53ef\u4ee5\u9009\u6216\u4e0d\u9009\u3002\u3002\u7136\u540e\u5c31\u53ef\u4ee5\u5217\u51fa\u65b9\u7a0b\u4e86\u3002\u3002\u5f88\u597d\u5217\u3002\u3002\u5c31\u4e0d\u5199\u4e86\u3002\u3002
\u65f6\u95f4\u590d\u6742\u5ea6\uff08money*N\uff09\u3002\u3002\u6ce8\u610f\u5230\u771f\u6b63\u6709\u7528\u7684money\u53ea\u670972000\u3002\u3002\u90a3\u4e48\u5c31\u8981600*72000\u7684\u7a7a\u95f4\u3002\u3002400\u591aMB\uff01\uff01
\uff08\u6211\u4e00\u5f00\u59cb\u7684\u6c99\u8336\u505a\u6cd5\uff09\u3002\u3002
2\uff1aBest\u505a\u6cd5\uff08100\u5206\uff09
\u65e2\u7136\u4e0d\u884c\u5c31\u53ea\u597d\u4f18\u5316\u963f\u3002\u3002
\u53ef\u4ee5\u53d1\u73b0\u524d\u9762\u662f\u6709\u6d6a\u8d39\u7684\u3002\u3002\u56e0\u4e3a\u5982\u679c\u4ece\u56e0\u4e3a\u5982\u679cDP[pos,have-1]=DP[pos,have]\u7684\u8bdd\u3002\u3002\u540e\u4e00\u4e2a\u6839\u672c\u6ca1\u5fc5\u8981\u5b58\u963f\u3002\u3002
\uff08\u4f4d\u7f6e\u4e00\u6837\u3002\u3002\u94b1\u8fd8\u591a\u4e00\u70b9\u3002\u3002\u6700\u591a\u80fd\u9009\u7684\u53cd\u800c\u4e00\u6837\u3002\u3002\u4e22\u4eba\u4e0d\u3002\u3002\u5b58\u4e86\u6709X\u7528\u963f\u3002\u3002\uff09..
\u6240\u4ee5\u53ea\u9700\u8981\u5b58what\u5462\uff1f\u53ea\u9700\u8981\u5b58DP[pos,have-1]<DP[pos,have]\u7684\u90a3\u4e9bhave\u5c31\u53ef\u4ee5\u4e86(\u4e5f\u5c31\u662f\u9009X\u4e2a\u7684\u8bdd\u6700\u5c11\u7684\u94b1\u3002\u3002\u56e0\u4e3a\u518d\u5c11\u5c31\u4e0d\u591f\u4e86)\u3002\u3002
\u90a3\u6837\u7684have\u6700\u591a\u6709N\u4e2a\u3002\u3002\u56e0\u4e3a\u6bcf\u4e2a\u6700\u591a\u80fd\u9009\u7684\u90fd\u4e0d\u7b49\u561b\u3002\u3002\u3002
\u6545\u8bbeDP[pos,X]\u4e3a\u4ecepos\u4e2a\u5f00\u59cb\u3002\u3002\u9009X\u4e2a\u6700\u5c11\u7684\u94b1\u3002\u3002\u3002
\u6545DP[pos,X]=min(DP[pos+1,X-(pos\u662f\u7259\u9f7f\u4e48\uff1f1\uff1a0)]+pos\u7684\u4ef7\u503c,DP[pos+\u4e0d\u9009pos\u800c\u8df3\u8fc7\u7684][X]);
\u7528\u8bb0\u5fc6\u5316\u641c\u7d22\u8981\u65b9\u4fbf\u4e00\u4e9b\u3002\u3002\u3002
\u90a3\u4e48\u5c31\u53ef\u4ee5\u4e00\u4e2a\u4e2aX\u8bd5\u8fc7\u53bb\u3002\u3002\u76f4\u5230\u5728\u603b\u5171\u4e2d\u9009X\u4e2a\u7684\u94b1\u5927\u4e8eP\u3002\u3002\u7136\u540eX-1\u5c31OK\u4e86\u3002\u3002
P.S
\u4e00\u5f00\u59cb\u6211\u5199\u7b2c\u4e00\u4e2a\u53d1\u73b0MLE\u3002\u3002\u6211\u4ee5\u4e3a\u7a7a\u95f4\u53ef\u80fd\u5b9e\u9645\u7528\u5230\u7684\u4e0d\u591a\u3002\u3002\u4e8e\u662f\u5f00hash\u3002\u3002\u7ed3\u679cSB\u6389\u4e86\u3002\u3002
\u770b\u6765\u6293\u4f4f\u95ee\u9898\u7684\u672c\u8d28\u7684\u80fd\u529b\u8fd8\u4e0d\u591f\u963f\u3002\u3002
\u8981\u8bb0\u5f55\u548c\u8f93\u51fa\u8def\u5f84\u963f\u3002\u3002\u6709\u70b9\u9ebb\u70e6\u7684\u3002\u3002
\u6240\u4ee5\u52a8\u89c4\u4e2d\u4e00\u4e2a\u91cd\u8981\u7684\u601d\u60f3\u4e00\u5b9a\u8981\u719f\u8bb0\u963f\u3002\u3002\u53ea\u4fdd\u7559\u6709\u7528\u7684\u72b6\u6001\uff01\uff01\uff01
\u5199\u4e86\u6211N\u4e45\u3002\u3002\u90c1\u95f7\u6b7b\u4e86\u3002\u3002
Code\u3002\u3002\u3002
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;
\/\/main data
const int maxn=601,inf=~0U>>2;
int N,K,P;
int S[maxn*2],C[maxn*2]={0};
struct edge
{
int t;edge* next;
edge(int tt,edge*nn):t(tt),next(nn){}
}*E[maxn];
void init()
{
cin>>N>>K>>P;
for(int i=1;i<=K;i++)
{
E[0]=new edge(i,E[0]);
cin>>C[i];
}
for(int i=1;i<=N;i++)
{
int f;
cin>>C[i+maxn]>>f;
E[f]=new edge(i+maxn,E[f]);
}
}
int ord[maxn],cnt=0;
int dfs(int t)
{
ord[cnt++]=t;
if(t>maxn) return S[t]=1;
for(edge*i=E[t];i;i=i->next)
S[t] += dfs(i->t);
return ++S[t];
}
\/\/hash
int DP[2*maxn][maxn+1];
bool Ch[2*maxn][maxn+1];
int dp(int pos,int ch)
{
if(DP[pos][ch]!=0)
return DP[pos][ch];
if(ch==0)
return 0;
if(pos>=cnt)
return DP[pos][ch]=inf;
int ind=ord[pos];
int a=dp(pos+1,ch-(ind>maxn?1:0) )+C[ind],b=dp(pos+S[ind],ch);
if(a<b){Ch[pos][ch]=true;DP[pos][ch]=a;}
else{Ch[pos][ch]=false;DP[pos][ch]=b;}
return DP[pos][ch];
}
int main()
{
init();
dfs(0);
memset(DP,0,sizeof(DP));
int i;
for(i=0;i<=N;i++)
if(dp(0,i)>P) break;
i–;
cout<<i<<endl;
if(i==N)
{
cout<<1;
for(int j=2;j<=N;j++)
cout<<" "<<j;
cout<<endl;
return 0;
}
int now=0,m=i;
bool first=true;
while(m)
{
if(Ch[now][m])
{
if(ord[now]>maxn)
{
m–;if(!first)cout<<" ";
cout<<ord[now]-maxn;first=false;
}
now++;
}
else
{
now+=S[ord[now]];
}
}
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u9053\u9898\u8fd8\u662f\u6709\u70b9\u96be\u7684\u62c9\u3002\u3002\uff08\u6211\u592a\u6c99\u8336\u4e86\u3002\u3002\uff09\u9996\u5148\u53ef\u4ee5\u770b\u6210\u6709\u4f9d\u8d56\u7684\u80cc\u5305\u95ee\u9898\u3002\u3002\u628a\u7259\u9f7f\u548c\u7259\u9f88\u90fd\u770b\u6210\u7269\u54c1\u3002\u3002\u7259\u9f7f\u82e5\u8981\u88ab\u9009\u5219\u653e\u4ed6\u7684\u7259\u9f88\u4e5f\u8981\u88ab\u9009\u3002\u3002\u4e0d\u5c31\u662f\u4f9d\u8d56\u4e48\u3002\u3002\u9996\u5148\u628a\u7269\u54c1\u91cd\u65b0\u6392\u4e00\u4e0b\u4f4d\u7f6e\uff08\u6211\u662f\u7528dfs\u7684\u3002\u3002\u770b\u6210\u6811\u7684\u8bdd\u3002\u3002dfs\u5e8f\u6b63\u597d\u6ee1\u8db3\u8981\u6c42\u4fc4\uff09\u3002\u3002\u628a\u7259\u9f7f\u90fd\u653e\u5728\u5b83\u4f9d\u8d56\u7684\u7259\u9f88\u7684\u540e\u9762\u3002\u3002\u518d\u5728\u5f00\u5934\u653e\u4e2a\u865a\u62df\u7269\u54c1\u3002\u3002\u65b9\u4fbf\u7f16\u7a0b\u3002\u3002\u3002\u8fd9\u6837\u4e0d\u9009\u7684\u8bdd\u5c31\u53ef\u4ee5\u5f80\u540e\u8df3\u8fc7\u90a3\u4e9b\u7259\u9f7f\u3002\u3002\u5c31\u53ef\u4ee5DP\u4e86\u6709\u4e24\u79cd\u505a\u6cd5\u3002\u3002\u4e4b\u95f4\u7684\u5bf9\u6bd4\u8fd8\u662f\u5f88\u6709\u610f\u4e49\u7684\u3002\u30021\uff1a\u6c99\u8336\u505a\u6cd5\uff0850\u5206\uff09\u8bbeDP[pos,have]\u4e3a\u4ece\u7b2cpos\u4e2a\u7269\u54c1\u5f00\u59cb\uff0c\u8fd8\u6709have\u7684money\u6700\u591a\u80fd\u9009\u51e0\u4e2a\u3002\u3002\u5219pos\u53ef\u4ee5\u9009\u6216\u4e0d\u9009\u3002\u3002\u7136\u540e\u5c31\u53ef\u4ee5\u5217\u51fa\u65b9\u7a0b\u4e86\u3002\u3002\u5f88\u597d\u5217\u3002\u3002\u5c31\u4e0d\u5199\u4e86\u3002\u3002\u65f6\u95f4\u590d\u6742\u5ea6\uff08money*N\uff09\u3002\u3002\u6ce8\u610f\u5230\u771f\u6b63\u6709\u7528\u7684money\u53ea\u670972000\u3002\u3002\u90a3\u4e48\u5c31\u8981600*72000\u7684\u7a7a\u95f4\u3002\u3002400\u591aMB\uff01\uff01\uff08\u6211\u4e00\u5f00\u59cb\u7684\u6c99\u8336\u505a\u6cd5\uff09\u3002\u30022\uff1aBest\u505a\u6cd5\uff08100\u5206\uff09\u65e2\u7136\u4e0d\u884c\u5c31\u53ea\u597d\u4f18\u5316\u963f\u3002\u3002\u53ef\u4ee5\u53d1\u73b0\u524d\u9762\u662f\u6709\u6d6a\u8d39\u7684\u3002\u3002\u56e0\u4e3a\u5982\u679c\u4ece\u56e0\u4e3a\u5982\u679cDP[pos,have-1]=DP[pos,have]\u7684\u8bdd\u3002\u3002\u540e\u4e00\u4e2a\u6839\u672c\u6ca1\u5fc5\u8981\u5b58\u963f\u3002\u3002\uff08\u4f4d\u7f6e\u4e00\u6837\u3002\u3002\u94b1\u8fd8\u591a\u4e00\u70b9\u3002\u3002\u6700\u591a\u80fd\u9009\u7684\u53cd\u800c\u4e00\u6837\u3002\u3002\u4e22\u4eba\u4e0d\u3002\u3002\u5b58\u4e86\u6709X\u7528\u963f\u3002\u3002\uff09..\u6240\u4ee5\u53ea\u9700\u8981\u5b58what\u5462\uff1f\u53ea\u9700\u8981\u5b58DP[pos,have-1]<DP[pos,have]\u7684\u90a3\u4e9bhave\u5c31\u53ef\u4ee5\u4e86(\u4e5f\u5c31\u662f\u9009X\u4e2a\u7684\u8bdd\u6700\u5c11\u7684\u94b1\u3002\u3002\u56e0\u4e3a\u518d\u5c11\u5c31\u4e0d\u591f\u4e86)\u3002\u3002\u90a3\u6837\u7684have\u6700\u591a\u6709N\u4e2a\u3002\u3002\u56e0\u4e3a\u6bcf\u4e2a\u6700\u591a\u80fd\u9009\u7684\u90fd\u4e0d\u7b49\u561b\u3002\u3002\u3002\u6545\u8bbeDP[pos,X]\u4e3a\u4ecepos\u4e2a\u5f00\u59cb\u3002\u3002\u9009X\u4e2a\u6700\u5c11\u7684\u94b1\u3002\u3002\u3002\u6545DP[pos,X]=min(DP[pos+1,X-(pos\u662f\u7259\u9f7f\u4e48\uff1f1\uff1a0)]+pos\u7684\u4ef7\u503c,DP[pos+\u4e0d\u9009pos\u800c\u8df3\u8fc7\u7684][X]);\u7528\u8bb0\u5fc6\u5316\u641c\u7d22\u8981\u65b9\u4fbf\u4e00\u4e9b\u3002\u3002\u3002\u90a3\u4e48\u5c31\u53ef\u4ee5\u4e00\u4e2a\u4e2aX\u8bd5\u8fc7\u53bb\u3002\u3002\u76f4\u5230\u5728\u603b\u5171\u4e2d\u9009X\u4e2a\u7684\u94b1\u5927\u4e8eP\u3002\u3002\u7136\u540eX-1\u5c31OK\u4e86\u3002\u3002P.S\u4e00\u5f00\u59cb\u6211\u5199\u7b2c\u4e00\u4e2a\u53d1\u73b0MLE\u3002\u3002\u6211\u4ee5\u4e3a\u7a7a\u95f4\u53ef\u80fd\u5b9e\u9645\u7528\u5230\u7684\u4e0d\u591a\u3002\u3002\u4e8e\u662f\u5f00hash\u3002\u3002\u7ed3\u679cSB\u6389\u4e86\u3002\u3002\u770b\u6765\u6293\u4f4f\u95ee\u9898\u7684\u672c\u8d28\u7684\u80fd\u529b\u8fd8\u4e0d\u591f\u963f\u3002\u3002\u8981\u8bb0\u5f55\u548c\u8f93\u51fa\u8def\u5f84\u963f\u3002\u3002\u6709\u70b9\u9ebb\u70e6\u7684\u3002\u3002\u6240\u4ee5\u52a8\u89c4\u4e2d\u4e00\u4e2a\u91cd\u8981\u7684\u601d\u60f3\u4e00\u5b9a\u8981\u719f\u8bb0\u963f\u3002\u3002\u53ea\u4fdd\u7559\u6709\u7528\u7684\u72b6\u6001\uff01\uff01\uff01\u5199\u4e86\u6211N\u4e45\u3002\u3002\u90c1\u95f7\u6b7b\u4e86\u3002\u3002Code\u3002\u3002\u3002#include<iostream>#include<ctype.h>#include<string.h>using namespace std;\/\/main dataconst int maxn=601,inf=~0U>>2;int N,K,P;int S[maxn*2],C[maxn*2]={0};struct edge{int t;edge* next;edge(int tt,edge*nn):t(tt),next(nn){}}*E[maxn];void init(){cin>>N>>K>>P;for(int i=1;i<=K;i++){E[0]=new edge(i,E[0]);cin>>C[i];}for(int i=1;i<=N;i++){int f;cin>>C[i+maxn]>>f;E[f]=new edge(i+maxn,E[f]);}}int ord[maxn],cnt=0;int dfs(int t){ord[cnt++]=t;if(t>maxn) return S[t]=1;for(edge*i=E[t];i;i=i->next)S[t] += dfs(i->t);return ++S[t];}\/\/hashint DP[2*maxn][maxn+1];bool Ch[2*maxn][maxn+1];int dp(int pos,int ch){ if(DP[pos][ch]!=0)return DP[pos][ch]; if(ch==0)return 0;if(pos>=cnt)return DP[pos][ch]=inf;int ind=ord[pos];int a=dp(pos+1,ch-(ind>maxn?1:0) )+C[ind],b=dp(pos+S[ind],ch); if(a<b){Ch[pos][ch]=true;DP[pos][ch]=a;}else{Ch[pos][ch]=false;DP[pos][ch]=b;}return DP[pos][ch];}int main(){init();dfs(0);memset(DP,0,sizeof(DP));int i;for(i=0;i<=N;i++)if(dp(0,i)>P) break;i–;cout<<i<<endl;if(i==N){cout<<1;for(int j=2;j<=N;j++)cout<<" "<<j;cout<<endl;return 0;}int now=0,m=i;bool first=true;while(m){if(Ch[now][m]){if(ord[now]>maxn){m–;if(!first)cout<<" ";cout<<ord[now]-maxn;first=false;}now++;}else{now+=S[ord[now]];}}}<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/8"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=8"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/8\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}