ARC083 E BichromeTree(700)

部分の最適化

木を小さく分けてずっと考えてると、最適解が１つだと分かる

速解きは無理

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define lol(i,n) for(int i=0;i<n;i++)
6. #define mod 1000000007
7. typedef long long ll;
8. using namespace std;
9. bool dp[5010],cop[5010];
10. vector<int> v[1010];
11. int index[1010];
12. int par[1010];
13. int x[1010],y[1010];
14. queue<int> Q;
15. int main(){
16. int n;
17. cin>>n;
18. lol(i,n)index[i]=0;
19. par[0]=-1;
20. for(int i=1;i<n;i++){
21. cin>>par[i];par[i]--;
22. index[par[i]]++;
23. v[par[i]].push_back(i);
24. }
25. for(int i=0;i<n;i++){
26. if(index[i]==0)Q.push(i);
27. }
28. lol(i,n){
29. cin>>x[i];
30. }
31. while(!Q.empty()){
32. int i=Q.front();Q.pop();
33. if(i==-1)break;
35. lol(k,5010)dp[k]=false;
36. dp[0]=true;
37. int sum=0;
38. int visize=v[i].size();
39. for(int k=0;k<visize;k++){
40. lol(r,5010)cop[r]=false;
41. int tmp=v[i][k];
42. sum+=x[tmp];
43. for(int r=0;r+x[tmp]<5010;r++){
44. cop[r+x[tmp]]|=dp[r];
45. }
46. for(int r=0;r+y[tmp]<5010;r++){
47. cop[r+y[tmp]]|=dp[r];
48. }
49. lol(r,5010)dp[r]=cop[r];
50. }
51. int maxi=-1;
52. for(int k=0;k<=min(sum,x[i]);k++)if(dp[k])maxi=k;
53. y[i]=sum-maxi;
54. //cout<<"%"<<i<<" "<<x[i]<<" "<<y[i]<<" "<<sum<<" "<<maxi<<endl;
55. if(y[i]<0||maxi==-1){
56. cout<<"IMPOSSIBLE"<<endl;
57. return 0;
58. }
60. index[par[i]]--;
61. if(index[par[i]]==0){
62. Q.push(par[i]);
63. }
64. }
65. cout<<"POSSIBLE"<<endl;
66. return 0;
67. }

実装の練習になった