Advertisement
Guest User

Untitled

a guest
May 20th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. import java.util.*;
  2. public class Main {
  3.  
  4. public static void main(String[] args) {
  5. Scanner sc = new Scanner(System.in);
  6. String prv = sc.next();
  7. String vtor = sc.next();
  8. String letters = sc.next();
  9. int[][] ceni = new int[letters.length() + 1][letters.length() + 1];
  10. for (int i = 0; i <= letters.length(); i++) {
  11. for (int j = 0; j <= letters.length(); j++) {
  12. ceni[i][j] = sc.nextInt();
  13. }
  14. }
  15. prv+=" ";
  16. vtor+=" ";
  17. Map<Character,Integer> mapa=new HashMap<>();
  18. mapa.put(' ',0);
  19. for (int i = 0; i < letters.length(); i++) {
  20. mapa.put(letters.charAt(i),i+1);
  21. }
  22. int num=Math.max(prv.length(),vtor.length())+1;
  23. int [][] dp=new int[num][num];
  24. dp[0][0]=ceni[0][0];
  25. for (int i = 1; i <=num ; i++) {
  26. int i1=Math.min(i,prv.length())-1;
  27. int i2=Math.min(i,vtor.length())-1;
  28. dp[i][0]=ceni[mapa.get(prv.charAt(i1))][0]+dp[i-1][0];
  29. dp[0][i]=ceni[mapa.get(prv.charAt(i2))][0]+dp[0][i-1];
  30. }
  31. int max=0;
  32. for (int i = 1; i <prv.length(); i++) {
  33. for (int j = 1; j < vtor.length(); j++) {
  34. // System.out.println(dp[i][j]+" ");
  35. dp[i][j]=Math.max(dp[i-1][j-1]+ceni[mapa.get(prv.charAt(i-1))][vtor.charAt(j-1)],dp[i-1][j]+ceni[mapa.get(prv.charAt(i-1))][0]);
  36. dp[i][j]=Math.max(dp[i][j],dp[i][j-1]+ceni[mapa.get(vtor.charAt(j-1))][0]);
  37.  
  38. }
  39. // System.out.println();
  40. }
  41. System.out.println(dp[num][num]);
  42. }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement