# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Here some of important algorithm are translated in English by GitHUB. Thanks! GitHUB.
But we need full English version of this site...Cause this site is just Stunning. Can anyone give me the link of this site where I get full English version of it???....PLZ..........
I just write here a structure for coin change problem:
433A — Kitahara Haruki's Gift
http://codeforces.net/problemset/problem/433/A
int recursion(int index, int amount){//initially index is 0, amount = amount of destination money
if(i >= total_types_of_Coin){//e.g:1c,5,10c = 3 types of coin here..
if(amount == 0)return 1;// base case else return 0;
}
int way1 = 0, way2 = 0;
if(dp[index][amount] != -3)dp[index][amount];//dp was memset by the value of -3 in main function
if(amount-Coin[index] >= 0)way1 = recursion(index, amount-Coin[index]);//if we get same coin for several times otherwise index will be (index+1) that means try next coins;
way2 = recursion(index+1, amount);
return dp[index][amount] = way1+way2;
}
try it...i think this will work for following problems... UVa — 357, 674, 11137, 562;
Don't be afraid this is not very difficult....
For new programmer, this is very essential... We know a little bit for that we don't answer many problem as like "largest sum contiguous sub array" that's really very easy to determine largest sum if we know the following algorithm.....
Initialize: max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0) max_ending_here = 0
(c) if(max_so_far < max_ending_here) max_so_far = max_ending_here
return max_so_far
Explanation: Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far
Lets take the example:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = max_ending_here = 0
for i=0, a[0] = -2 max_ending_here = max_ending_here + (-2) Set max_ending_here = 0 because max_ending_here < 0
for i=1, a[1] = -3 max_ending_here = max_ending_here + (-3) Set max_ending_here = 0 because max_ending_here < 0
for i=2, a[2] = 4 max_ending_here = max_ending_here + (4) max_ending_here = 4 max_so_far is updated to 4 because max_ending_here greater than max_so_far which was 0 till now
for i=3, a[3] = -1 max_ending_here = max_ending_here + (-1) max_ending_here = 3
for i=4, a[4] = -2 max_ending_here = max_ending_here + (-2) max_ending_here = 1
for i=5, a[5] = 1 max_ending_here = max_ending_here + (1) max_ending_here = 2
for i=6, a[6] = 5 max_ending_here = max_ending_here + (5) max_ending_here = 7 max_so_far is updated to 7 because max_ending_here is greater than max_so_far
for i=7, a[7] = -3 max_ending_here = max_ending_here + (-3) max_ending_here = 4
Code :
for(int i = 0; i < N; i++){
max_ending_here += Number[i]; if(max_ending_here > max_so_far)max_so_far = max_ending_here; if(max_ending_here < 0)max_ending_here = 0; }
So the complexity for this code is O(n)...
Happy coding...:)
Name |
---|