http://www.spoj.com/problems/ALICESIE/
Problem description may seem complicated. But if you try out test cases for n=2,3,4 till 10 you will find the pattern
Just in couple of lines you can finish the program
🙂
for n= 2 –>1
n=3 –> 2
n=4–>2
n=5–>3
n=6–>3
n=7–>4
n=8–>8
This is an interesting and easy DP problem. I solved this in less than 5 minutes.(Trust me ! Its that easy)
Let
dp[i] –> maximum coin sum till i monsters
dp[i]=max(arr[i]+solve(i+2),solve(i+1));
Case 1:
if you choose the ith monster’s coins you cannot choose the next so you
move to the i+2th monster.
Case 2:
if you do not choose the ith monster’s coins you still have a chance to choose i+1th monster’s coins.So you move to i+1th monster
[gist https://gist.github.com/anonymous/8433780]Yet another Knapsack based problem
| #include <vector> | |
| #include <list> | |
| #include <map> | |
| #include <set> | |
| #include <deque> | |
| #include <queue> | |
| #include <stack> | |
| #include <bitset> | |
| #include <algorithm> | |
| #include <functional> | |
| #include <numeric> | |
| #include <utility> | |
| #include <sstream> | |
| #include <iostream> | |
| #include <iomanip> | |
| #include <cstdio> | |
| #include <cmath> | |
| #include <cstdlib> | |
| #include <ctime> | |
| #include <cstring> | |
| #include <climits> | |
| #include <stdlib.h> | |
| using namespace std; | |
| #define REP(i,n) for(int i=0; i<n; i++) | |
| #define FOR(i,st,end) for(int i=st;i<end;i++) | |
| #define db(x) cout << (#x) << " = " << x << endl; | |
| #define mp make_pair | |
| #define pb push_back | |
| int n,W,wt[1001]; | |
| int dp[1001][1001]; | |
| int solve(int i,int w){ | |
| if(i>n) | |
| return w; | |
| if (dp[i][w]!=-1) | |
| return dp[i][w]; | |
| if((wt[i]+w)<=W) | |
| dp[i][w]=max(solve(i+2,w+wt[i]),solve(i+1,w)); | |
| else | |
| dp[i][w]=solve(i+1,w); | |
| return dp[i][w]; | |
| } | |
| int main(){ | |
| int t; | |
| scanf("%d",&t); | |
| FOR(j,1,t+1){ | |
| scanf("%d %d",&n,&W); | |
| FOR(i,1,n+1){ | |
| scanf("%d",&wt[i]); | |
| } | |
| memset(dp,-1,sizeof dp); | |
| printf("Scenario #%d: %d\n",j,solve(1,0)); | |
| } | |
| } |
A good dynamic programming practice 🙂
[gist https://gist.github.com/vishnujayvel/8234900]
coding hangover 