Problem with DP in round #383 problem D (div 2)

Revision en3, by Lance_HAOH, 2016-12-11 03:31:36

I am trying to solve round #383 problem D (div 2):

Problem statement:here

I can complete every step up till the usage of DP. In my code, I used 2-D DP like what was mentioned in the editorial. Somehow, my code is failing the following test case:

10 5 100
6 18 35 6 87 58 4 53 37 71
465782 57034 547741 748298 315223 370368 679320 349012 9740 622511
1 2
10 9
6 7
3 6
7 1

Expected Output: 2050129 My Program Output: 1836591

My attempt:

#include <iostream>
#include <vector>
#include <unordered_map>
//#define debug
using namespace std;

#define ll long long
#define v64 vector<ll>
#define um unordered_map<ll,ll>
#define mp make_pair

ll n,m,w,a,b;

typedef struct woman {
	ll w, b;
} woman;

woman ww[1005];
ll par[1005], rk[1005],dp[1005][1005];
um cw, cb;
int val[1005];

ll find(ll x) {
	ll p = x;
	if(par[x]!=x) p = find(par[x]);
	return par[x] = p;
}

inline void un(ll x,ll y) {
	ll px = find(x), py = find(y);
	if(px != py) {
		if(rk[px] > rk[py]) {
			par[py] = px;
			rk[px] += rk[py];
 		} else {
			par[px] = py;
			rk[py] += rk[px];
		}
	}
}

ll solve(ll cur, ll t) {
	if(dp[cur][t]!=-1) return dp[cur][t];
	if(cur <= n && t>0) {
		if(ww[cur].w<=t) {
			if(val[find(cur)]) {	
				val[find(cur)] = 0;
				ll a1  = 0;
				if(cw[find(cur)]<=t) a1 = cb[find(cur)]+solve(cur+1,t-cw[find(cur)]);
				ll a2 = ww[cur].b+solve(cur+1,t-ww[cur].w);
				val[find(cur)] = 1;
				ll a3 = solve(cur+1,t);
				return dp[cur][t] = max(a1,max(a2,a3));
			} else {
				return dp[cur][t] = solve(cur+1,t);
			}
		} else {
			return dp[cur][t] = solve(cur+1,t);
		}
	}
	return dp[cur][t]=0;
}

int main(void) {
	#ifdef debug
		freopen("in","r",stdin);
	#else
		ios_base::sync_with_stdio(false);
		cin.tie(0);
	#endif
	cin >> n >> m >> w;
	fill_n(rk,n+1,1);
	fill_n(val,n+1,1);
	for(int i = 1; i <= n; ++i) fill_n(dp[i],w+1,-1);

	for(int i = 1; i <= n; ++i) {
		cin >> ww[i].w;
		par[i] = i;
	}
	for(int i = 1; i <= n; ++i) {
		cin >> ww[i].b;
	}
	for(int i = 1; i <= m; ++i) {
		cin >> a >> b;
		un(a,b);
	}
	for(int i = 1 ; i <= n; ++i) {
                cw[find(i)] += ww[i].w;
                cb[find(i)] += ww[i].b;
        }
	cout << solve(1,w) << endl;
	return 0;
}

If I remove the DP (from the solve function), my program will pass the test case. Hence, it is clear that my DP is wrong. However, I do not know how to write the DP properly. Could someone please advise me on why my code is wrong?

Tags #round #383, #dp, #unionfind, #problem d

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Lance_HAOH 2016-12-11 03:31:36 20
en2 English Lance_HAOH 2016-12-10 18:29:58 156
en1 English Lance_HAOH 2016-12-10 18:28:37 2644 Initial revision (published)