Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- String prv = sc.next();
- String vtor = sc.next();
- String letters = sc.next();
- int[][] ceni = new int[letters.length() + 1][letters.length() + 1];
- for (int i = 0; i <= letters.length(); i++) {
- for (int j = 0; j <= letters.length(); j++) {
- ceni[i][j] = sc.nextInt();
- }
- }
- prv+=" ";
- vtor+=" ";
- Map<Character,Integer> mapa=new HashMap<>();
- mapa.put(' ',0);
- for (int i = 0; i < letters.length(); i++) {
- mapa.put(letters.charAt(i),i+1);
- }
- int num=Math.max(prv.length(),vtor.length())+1;
- int [][] dp=new int[num][num];
- dp[0][0]=ceni[0][0];
- for (int i = 1; i <=num ; i++) {
- int i1=Math.min(i,prv.length())-1;
- int i2=Math.min(i,vtor.length())-1;
- dp[i][0]=ceni[mapa.get(prv.charAt(i1))][0]+dp[i-1][0];
- dp[0][i]=ceni[mapa.get(prv.charAt(i2))][0]+dp[0][i-1];
- }
- int max=0;
- for (int i = 1; i <prv.length(); i++) {
- for (int j = 1; j < vtor.length(); j++) {
- // System.out.println(dp[i][j]+" ");
- 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]);
- dp[i][j]=Math.max(dp[i][j],dp[i][j-1]+ceni[mapa.get(vtor.charAt(j-1))][0]);
- }
- // System.out.println();
- }
- System.out.println(dp[num][num]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement