Sequence maximum return

Title Description
Given a length of m Integer sequence of a1,a2,…,am.

The value of each element in the sequence ai All meet 1≤ai≤n.

When a value is i The element and a value of j When elements of are adjacent , The benefits that can be generated are wi,j.

Now? , We can delete up to from the sequence k Elements , After deleting some elements , Elements that are not adjacent may become adjacent .

The sum of the proceeds of the sequence is the sum of the proceeds generated by all adjacent element pairs , For example, a length of 3 Integer sequence of 1,3,2 The income and w1,3+w3,2.

Excuse me, , By using the delete operation , What is the maximum return sum of the sequence that can be obtained ？

Input format
The first line contains three integers n,k,m.

The second line contains m It's an integer a1,a2,…,am.

Next n That's ok , Each row contains n It's an integer , Among them the first i Xing di j The number of columns represents wi,j.

Output format
The maximum return and of the output sequence .

Data range
about 30% The data of ,1≤n,k,m≤20.
about 100% The data of ,1≤n,k,m≤200,0≤wi,j≤107,1≤ai≤n.
Data assurance wi,j=wj,i,wi,i=0.

 Examples 
 sample input ：
4 1 3
1 4 2
0 3 0 1
3 0 0 0
0 0 0 0
1 0 0 0
 sample output ：
3
 Sample explanation 
 The sum of the initial sequence returns is  w1,4+w4,2=1+0=1.

 Delete the middle  4  after , Sequence  1,2  The income and  w1,2=3.

Train of thought ： DP
Think back to finding the longest ascending subsequence ：

use f[j] Before presentation j Number , And take the second j The longest ascending subsequence with the ending number .
This topic ：
f[i][j] To express consideration in the form of i The number is the end , Delete j The maximum benefit of the number .

Suppose you delete j After the count , and i The adjacent number is the u Number .

u and i adjacent , u + 1 To i - 1 Be deleted , Deleted i - 1 - u Number , Had in 1 To u Delete again in j - (i - 1 - u) Number .

therefore ：f[i][j] = max (f[u, j - (i - 1 - u)] + w[a[u], a[i]]), // State transition equation
among ：j - (i - 1 - u) >= 0 And u <= i - 1 And j - (i - 1 - u) <= u.

Explanation of value range ：

j - (i - 1 - u) >= 0： front u In number , The number of deleted numbers must be greater than or equal to 0 .

u <= i - 1 ： u The biggest is i - 1.

j - (i - 1 - u) <= u : front u In number , The maximum number of deleted is u individual .

Time complexity O(n^3)
reference
C++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 240;
int n,m,k,res;
int a[N],w[N][N],f[N][N];
int main()
{
    cin>>n>>k>>m;
    for (int i = 1; i <= m; i ++ )cin>>a[i];
    for (int i = 1; i <= n; i ++ )
     for (int j = 1;j <= n; j ++ )
      cin>>w[i][j];
    f[1][0]=0;
    for (int i = 1; i <= m; i ++ )
      for (int j = 0; j <= k ; j ++ )
        for (int u = 1; u < i; u ++ )
            if(j>=i - u -1)
           f[i][j]=max(f[i][j],f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
    for (int i = 0; i <= k; i ++ )
       res=max(res,f[m][i]);
    return cout<<res,0;
}

Java Code

import java.util.*;
import java.io.*;
public class Main{
    static int res;
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n=cin.nextInt(),k=cin.nextInt(),m=cin.nextInt();
        int a[]=new int [240];
        int f[][]=new int [240][240];
        int w[][]=new int [240][240];
        for(int i = 1; i <= m; i++ )a[i]=cin.nextInt();
        for(int i = 1; i<= n; i ++ )
           for(int j = 1; j<= n; j ++)
             w[i][j]=cin.nextInt();
        f[1][0]=0;
        for (int i = 1; i <= m; i ++ )
          for (int j = 0; j <= k ; j ++ )
            for (int u = 1; u < i; u ++ )
               if(j>=i - u -1)
               f[i][j]=Math.max(f[i][j],f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
        for (int i = 0; i <= k; i ++ )
        res=Math.max(res,f[m][i]);
        System.out.println(res);
        return ;
    }
}

GO Code

package main
import "fmt"
const N=240 
var (
   a[N]int 
   w[N][N]int 
   f[N][N]int 
)
func main(){
    var n,k,m,res int
    fmt.Scanf("%d %d %d",&n,&k,&m)
    for i:= 1;i <= m; i ++ {
        fmt.Scanf("%d",&a[i])
    }
    for i:= 1; i <= n; i ++ {
        for j:= 1; j <= n; j ++ {
            fmt.Scanf("%d",&w[i][j])
        }
    }
    f[1][0]=0
    for i:= 1; i <=m; i ++ {
       for j:= 0; j<=k; j ++ {
          for u:= 1; u < i; u ++ {
              if j>= i - u - 1{
                  f[i][j] = max(f[i][j], f[u][j - (i - u - 1)] + w[a[u]][a[i]])
              }
          }
       }   
    }
    for i:= 0; i <= k; i ++ {
        res = max(res,f[m][i]) 
    }
    fmt.Println(res)
}
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}

Train of thought two ： DP
Another way of thinking ：f[i][j] Said to i Bit end , Delete at most j The maximum benefit of the number
Define an enumeration variable p Express j
from i The subscript of the first undeleted number is i-p-1
The rest can be deleted at most j-p Number
The weight becomes w[a[i-p-1]][a[i]]
State transition equation ：f[i][j]=max(f[i][j],f[i-p-1][j-p]+w[a[i-p-1]a[i]]);
The answer to this question is f[m][k];

Time complexity O(n^3)
reference
C++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m,k;
int w[N][N],f[N][N],a[N];
int main()
{
    cin>>n>>k>>m;
    for (int i = 1; i <= m; i ++ )cin>>a[i];
    for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= n; j ++ )
         cin>>w[i][j];
    for (int i = 1; i <= m; i ++ )
      for (int j = 0; j <= k; j ++ )
         for(int p = 0; p <=j; p ++ )
           if(i-p-1>=0)
             f[i][j]=max(f[i][j],f[i-p-1][j-p]+w[a[i-p-1]][a[i]]);
    return cout<<f[m][k],0;
}

Java Code

import java.util.*;
import java.io.*;
public class Main{
    static int res;
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n=cin.nextInt(),k=cin.nextInt(),m=cin.nextInt();
        int a[]=new int [240];
        int f[][]=new int [240][240];
        int w[][]=new int [240][240];
        for(int i = 1; i <= m; i++ )a[i]=cin.nextInt();
        for(int i = 1; i<= n; i ++ )
           for(int j = 1; j<= n; j ++)
             w[i][j]=cin.nextInt();
        for (int i = 1; i <= m; i ++ )
          for (int j = 0; j <= k ; j ++ )
             for(int p = 0; p <=j; p ++ )
               if(i-p-1>=0)
             f[i][j]=Math.max(f[i][j],f[i-p-1][j-p]+w[a[i-p-1]][a[i]]);
        System.out.println(f[m][k]);
        return ;
    }
}

GO Code

package main
import "fmt"
const N=240 
var (
   a[N]int 
   w[N][N]int 
   f[N][N]int 
)
func main(){
    var n,k,m int
    fmt.Scanf("%d %d %d",&n,&k,&m)
    for i:= 1;i <= m; i ++ {
        fmt.Scanf("%d",&a[i])
    }
    for i:= 1; i <= n; i ++ {
        for j:= 1; j <= n; j ++ {
            fmt.Scanf("%d",&w[i][j])
        }
    }
    f[1][0]=0
    for i:= 1; i <=m; i ++ {
       for j:= 0; j<=k; j ++ {
          for p:= 0; p <= j; p ++ {
              if i - p - 1>= 0{
                   f[i][j]=max(f[i][j],f[i-p-1][j-p]+w[a[i-p-1]][a[i]])
              }
          }
       }   
    }
    fmt.Println(f[m][k])
}
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}

Welcome to leave a message like