20分,思路哪里错了,求解

P1064 [NOIP2006 提高组] 金明的预算方案

特大号的黑音 @ 2017-06-17 10:33:57

用结构体+DP写的 不懂思路上哪里错了

#include <bits/stdc++.h>
using namespace std;
struct PART{
  int v, w, q;
  vector<int> son;
};
const int maxn =  50000;
int n, m;
vector<PART> parts;
int dp[maxn];
int main(){
  freopen("out.txt","w",stdout);
  cin >> n >> m;
  for(int i = 0; i< m; i++){
    int v, w, q;
    cin >> v >> w >> q;
    parts.push_back((PART){v, w, q});
    parts[i].w *= v;
    if(q)
      parts[q].son.push_back(i);
  }
  for(int i = 0; i < m; i++){
    for(int j = n; j >= parts[i].v; j--){
      printf("i = %d, j = %d, v = %d\n", i , j, parts[i].v);
      if(!parts[i].q){
    dp[j] = max(dp[j], dp[j - parts[i].v] + parts[i].w);
    if(int k = parts[i].son.size() == 1){
      dp[j] = max(dp[j], dp[j - parts[i].v - parts[parts[i].son[0]].v] +
              parts[parts[i].son[0]].w);
    }
    else if(k == 2){
      if(j - parts[i].v - parts[parts[i].son[0]].v > 0)
        dp[j] = max(dp[j], dp[j - parts[i].v - parts[parts[i].son[0]].v] +
            parts[parts[i].son[0]].w);
      if(j - parts[i].v - parts[parts[i].son[1]].v > 0)
        dp[j] = max(dp[j], dp[j - parts[i].v - parts[parts[i].son[1]].v] +
            parts[parts[i].son[1]].w);
      if(j - parts[i].v - parts[parts[i].son[0]].v -

parts[parts[i].son[1]].v > 0) dp[j] = max(dp[j], dp[j - parts[i].v - parts[parts[i].son[0]].v -

parts[parts[i].son[1]].v] + parts[parts[i].son[0]].w +

            parts[parts[i].son[1]].w );
    }
    printf("dp[%d] = %d\n", j, dp[j]);
      }
      else
    continue;
    }
  }
  cout << dp[n];
  return 0;
}

by Windows_XP @ 2017-06-17 10:47:17

再写一遍说不定就对了

或者可能是rp不好


|