题解 | 小红的双生英雄

package main

import (
    "fmt"
)

func main() {
    var n,c,m int
    fmt.Scanf("%d %d %d",&n,&c,&m)
    cost := make([]int, n+1)
    value := make([]int, n+1)
    for i:=0;i<n;i++{
        fmt.Scanf("%d %d",&cost[i], &value[i])
    }
    pair := make([][]int, n+1)
    valuep := make([][]int, n+1)
    book := make([]bool, n+1)
    for i:=0;i<m;i++{
        var x,y,v int
        fmt.Scanf("%d %d %d", &x,&y,&v)
        x--
        y--
        pair[x] = append(pair[x], y)
        pair[y] = append(pair[y], x)
        valuep[x] = append(valuep[x], v)
        valuep[y] = append(valuep[y], v)
        book[max(x,y)] = true
    }
    f := [5][]int{}
    for i:=0;i<=4;i++{
        f[i] = make([]int, c+1)
    }
    for i:=0;i<n;i++{
        if book[i]{
            continue
        }
        for p:=4;p>0;p--{
            for j:=c;j>=cost[i];j--{
                if len(pair[i])!=0{
                    y := pair[i][0]
                    v := valuep[i][0]
                    if j>=cost[y]{
                        f[p][j] = max(f[p][j], f[p-1][j-cost[y]]+value[y])
                    }
                    if j>=cost[i]+cost[y]&&p>=2{
                        f[p][j] = max(f[p][j], f[p-2][j-cost[i]-cost[y]]+value[i]+value[y]+v)
                    }
                }
                f[p][j] = max(f[p][j], f[p-1][j-cost[i]]+value[i])
                //fmt.Println(i,j,f[j])
        }
        }
    }
    fmt.Println(max(f[1][c], max(f[2][c], max(f[3][c], f[4][c]))))
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}