Skip to content

Commit 61d07aa

Browse files
committed
Learning DP
1 parent 4ca69f7 commit 61d07aa

File tree

2 files changed

+78
-0
lines changed

2 files changed

+78
-0
lines changed

src/Codeforces/CutRibbon.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Codeforces;
2+
3+
import java.io.*;
4+
import java.util.ArrayList;
5+
6+
public class CutRibbon {
7+
static ArrayList<Integer> ls;
8+
static int[] dp;
9+
public static void main(String[] args)throws IOException {
10+
11+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
12+
13+
String[] s = br.readLine().split(" ");
14+
int n = Integer.parseInt(s[0]);
15+
int a = Integer.parseInt(s[1]);
16+
int b = Integer.parseInt(s[2]);
17+
int c = Integer.parseInt(s[3]);
18+
ls = new ArrayList<>();
19+
ls.add(a);
20+
ls.add(b);
21+
ls.add(c);
22+
23+
24+
dp = new int[n + 1];
25+
for(int i=1; i<=n; i++){
26+
if(i%a == 0 || i%b == 0 || i%c == 0)dp[i] = 1; //Initialize the dp values to 1 for all the multiples of a , b, c
27+
} //since this are the only values we will use
28+
int ans = ribbonCutting(n, ls); //and this pieces can finally reduce to smaller a, b, c values.
29+
System.out.println(ans);
30+
31+
}
32+
33+
private static int ribbonCutting(int n, ArrayList<Integer> ls){
34+
35+
for(int i=1; i<=n; i++){
36+
for(int j:ls){
37+
if(i-j >= 0 && dp[i-j] != 0){
38+
dp[i] = Math.max(dp[i], dp[i-j]+1);
39+
}
40+
}
41+
}
42+
43+
44+
return dp[n];
45+
}
46+
}

src/Codeforces/KefaandFirstSteps.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package Codeforces;
2+
import java.io.*;
3+
import java.util.Arrays;
4+
5+
public class KefaandFirstSteps {
6+
public static void main(String[] args)throws IOException {
7+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
8+
9+
int n = Integer.parseInt(br.readLine());
10+
String[] s = br.readLine().split(" ");
11+
int[] a = new int[s.length];
12+
13+
for(int i=0; i<s.length; i++)a[i] = Integer.parseInt(s[i]);
14+
int[] dp = new int[s.length];
15+
Arrays.fill(dp,1);
16+
17+
int ans = longestSubsegment(a,dp);
18+
System.out.println(ans);
19+
}
20+
21+
private static int longestSubsegment(int[] a, int[] dp){
22+
int max = 1;
23+
for(int i=1; i<a.length; i++){
24+
if(a[i] >= a[i-1]){
25+
dp[i] = dp[i-1] + 1;
26+
}
27+
if(max < dp[i])max = dp[i];
28+
}
29+
30+
return max;
31+
}
32+
}

0 commit comments

Comments
 (0)