A. 牛牛选物
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 返回总体积为V若干物品的最大总重量,如果g存在选择若干物品总体积为V的情况,返回-1
* @param v int整型一维数组
* @param g int整型一维数组
* @param V int整型
* @return int整型
*/
int res = -1;
int n = 0;
void dfs(int u, int cur, int pro, int[] g, int[] v, int lim){
if(cur > lim) return;
if(u == n){
if(cur == lim){
res = Math.max(res, pro);
}
return;
}
if(cur + v[u] <= lim){
dfs(u+1, cur+v[u], pro+g[u], g, v, lim);
}
dfs(u+1, cur, pro, g, v, lim);
}
public int Maximumweight(int[] v, int[] g, int V) {
// write code here
n = v.length;
dfs(0, 0, 0, g, v, V);
return res;
}
}
B. 牛牛与字符串2
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 给定一个字符串s,返回具有相同前缀后缀的子串的第二大长度,反之,返回-1即可。
* @param s string字符串 代表题意中的字符串s
* @return int整型
*/
public int[] get_next(String p){
int n = p.length();
int[] ne = new int[n + 1];
for(int i=2, j=ne[i-1]; i<=n; i++){
while(j != 0 && p.charAt(i-1) != p.charAt(j)) j = ne[j];
if(p.charAt(i-1) == p.charAt(j)) j ++;
ne[i] = j;
}
return ne;
}
public int solve (String s) {
// write code here
int n = s.length();
int[] ne = get_next(s);
int res = ne[n];
return res == 0? -1:res;
}
}
C. 牛牛送快递
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param n int整型 有n个城市
* @param m int整型 有m条路径
* @param s int整型 起始城市坐标
* @param t int整型 终点城市坐标
* @param edge int整型二维数组 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
* @return int整型
*/
int E = 510, N = 1010, INF = 0x3f3f3f3f, MOD = 1000000007;
int be, ed;
int[][] C = new int[N][N];
double[][] g = new double[E][E]; // g[a][b]存储a -> b的C值的对数值
int[][] rg = new int[E][E]; // rg[a][b]存储a -> b的C值的真实值
double[] L = new double[N]; // L[i] => 存储i!的对数值
double[] dist = new double[N]; // 用于存储对数距离
int[] rdist = new int[N]; // 用于存储真实距离
boolean[] st = new boolean[N];
public void getC(int n){
for(int i=0; i<=n; i++){
for(int j=0; j<=i; j++){
if(j == 0) C[i][j] = 1;
else C[i][j] = (int)(((long)C[i-1][j] + C[i-1][j-1]) % MOD);
}
}
}
public int Dijkstra(int n){
Arrays.fill(dist, INF);
rdist[be] = 1;
dist[be] = 0;
for(int i=0; i<n; i++){
// 找到最短距离的点
int t = -1;
for(int j=1; j<=n; j++){
if(!st[j] && (t == -1 || dist[j] < dist[t])){
t = j;
}
}
if(st[t]) continue;
st[t] = true;
// 用这个点的距离更新其它节点
for(int j=1; j<=n; j++){
if(dist[j] > dist[t] + g[t][j]){
dist[j] = dist[t] + g[t][j];
rdist[j] = (int)((long)rdist[t] * rg[t][j] % MOD);
}
}
}
return rdist[ed];
}
public int minDist (int n, int m, int s, int t, int[][] edge) {
// write code here
be = s; ed = t;
getC(N - 1);
// 预处理L数组
for(int i=1; i<N; i++) L[i] = L[i-1] + Math.log(i);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i == j){
g[i][j] = 0;
rg[i][j] = 1;
}
else {
rg[i][j] = 0;
g[i][j] = INF;
}
}
}
// 加边
for(int[] cur : edge){
int a = cur[0];
int b = cur[1];
int rc = C[cur[2]][cur[3]]; // 获取实际的消耗
double c = L[cur[2]] - L[cur[3]] - L[cur[2]-cur[3]];
g[a][b] = g[b][a] = c;
rg[a][b] = rg[b][a] = rc;
}
return Dijkstra(n);
}
}