[HDU-1561]The more,The Better[木の上でリュックサックに頼る思考]
50884 ワード
ACboyは戦略ゲームが大好きで、1つの地図の上で、Nつの城があって、すべての城はすべて一定の宝物があって、毎回ゲームの中でACboyはMつの城を攻略して中の宝物を得ることを許可します.しかし、地理的な理由で、直接攻略できない城もあります.これらの城を攻略するには、まず他の特定の城を攻略しなければなりません.できるだけ多くの宝物を手に入れるにはどのM城を攻略すべきか、ACboyに計算してもらえますか?Inputの各試験例は、まず2つの整数、N,M.(1<=M<=N<=200)を含む.次のN行では、各行に2つの整数が含まれ、a,b.i行目では、aはi番目の城を攻略するにはまずa番目の城を攻略しなければならないことを表し、a=0であればi番目の城を直接攻略することができることを表す.bはi番目の城の宝物の数を表し、b>=0である.N=0でM=0入力が終了します.Outputはテストインスタンスごとに、ACboyがM個の城を攻略して得た最も多くの宝物の数を表す整数を出力する.Sample Input 3 2 0 1 0 2 0 3 7 4 2 0 1 0 4 2 7 1 7 6 2 0 Sample Output 5 13題意:裸の木の上でリュックサックに依存する.この問題をする前にリュックサックを9回復習してもいいです.
思考1:リュックサックを用いる思想ここでは、各点を1つの汎化物として、下から上へ汎化物の合併を行うことができる.任意の2つの汎化物を合併する時間の複雑度はo(V∗V)o(V*V)o(V∗V)であり、合計n点であるため、全体の時間の複雑度はo(V∗V∗N)o(V*V*N)o(V∗V∗N)である.この考えも最も考えやすいが、時間の複雑さはやや高い.コード#コード#
思考二:ネット上にはdfsシーケンスを用いる巧みな方法があり、d p[i][j]dp[i][j]dp[i][j]dp[i][j]はi番目の点および以降のdfsシーケンスの大きさがjのインターフェースブロックの最大重み値を表す.そして、x:dfsシーケンスiに対応する点d p[i][j]=m a x(dp[i+1][j−1]+v a l[x],d p[i+s z[x][j])dp[i][j]=max(dp[i+1][j−1]+val[x],dp[i+sz[x]][j])dp[i][j]=max(dp[i+1][j−1]+val[x],dp[i+1][j]+j])
コード#コード#
思考:抽象は1つのテンプレートです:問題:1つの森にあげて、すべての点はすべて重量と価値があって、しかも1つのノードを買いたいならば、必ずその父のノードを買ったことがあって、今1つの容量Vのリュックサックがあって、得ることができる最大の価値を聞きます.(私达は1つのスーパーソースを創立して、このように1つの木の問題に転化しました)コード
思考1:リュックサックを用いる思想ここでは、各点を1つの汎化物として、下から上へ汎化物の合併を行うことができる.任意の2つの汎化物を合併する時間の複雑度はo(V∗V)o(V*V)o(V∗V)であり、合計n点であるため、全体の時間の複雑度はo(V∗V∗N)o(V*V*N)o(V∗V∗N)である.この考えも最も考えやすいが、時間の複雑さはやや高い.コード#コード#
#include
", dp[rt][m]);
}
return 0;
}
思考二:ネット上にはdfsシーケンスを用いる巧みな方法があり、d p[i][j]dp[i][j]dp[i][j]dp[i][j]はi番目の点および以降のdfsシーケンスの大きさがjのインターフェースブロックの最大重み値を表す.そして、x:dfsシーケンスiに対応する点d p[i][j]=m a x(dp[i+1][j−1]+v a l[x],d p[i+s z[x][j])dp[i][j]=max(dp[i+1][j−1]+val[x],dp[i+sz[x]][j])dp[i][j]=max(dp[i+1][j−1]+val[x],dp[i+1][j]+j])
コード#コード#
#include
"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = (int)1000 + 11;
const int M = (int)1000 + 11;
const int MOD = (int)1e9 + 7;
const int INF = (int)0x3f3f3f3f;
const ll INFF = (ll)0x3f3f3f3f3f3f3f3f;
/*-----------------------------------------------------------*/
vector<int> ve[N];
int in[N], out[N], sz[N], rid[N];
int val[N];
int clo;
void dfs(int u) {
in[u] = ++clo;
rid[clo] = u;
sz[u] = 1;
for (auto &v : ve[u]) {
dfs(v);
sz[u] += sz[v];
}
out[u] = clo;
}
int dp[N][M];
int main() {
int n, m;
while (cin >> n >> m) {
if(n == 0 && n == m) break;
memset(val, 0, sizeof(val));
for (int i = 0; i <= n; i++)
ve[i].clear();
rep(i, 1, n + 1) {
static int a, b;
cin >> a >> b;
ve[a].push_back(i);
val[i] = b;
}
clo = 0;
dfs(0); // dfs
// rep(i, 0, n + 1) { cout << i << " " << in[i] << " " <<
// out[i] << " " << sz[i] << "
"; }
memset(dp, 0, sizeof(dp));
for(int i = 2; i <= 2*m; i++) dp[clo][i] = -INF; dp[clo][1] = val[rid[clo]]; //
m++;
for (int i = clo - 1; i > 0; i--) {
int x = rid[i];
dp[i][1] = max(val[x], dp[i + sz[x]][1]);
for (int j = 2; j <= m; j++) {
dp[i][j] = max(dp[i + sz[x]][j], dp[i + 1][j - 1] + val[x]);
// cout << i << " " << j << " " << dp[i][j] << "
";
}
// dbg(dp[i][1]);
}
cout << dp[1][m] << "
";
}
return 0;
}
思考:抽象は1つのテンプレートです:問題:1つの森にあげて、すべての点はすべて重量と価値があって、しかも1つのノードを買いたいならば、必ずその父のノードを買ったことがあって、今1つの容量Vのリュックサックがあって、得ることができる最大の価値を聞きます.(私达は1つのスーパーソースを創立して、このように1つの木の問題に転化しました)コード
/***********************************************
Author :lzs
Created Time :2018 10 09 19 32 05
File Name :yy.cpp
************************************************/
#include
";
}
return 0;
}