4956

2小时前
import java.util.*;
public class Main{
static int N = 12, M = 1<<10, K = 110, n, m;
static long f[][][] = new long[N][K][M];
static int cnt[] = new int[M];
static ArrayList<Integer> state = new ArrayList<Integer>();
static ArrayList<Integer> match[] = new ArrayList[M];

static boolean check(int x){
for(int i = 0; i < n; i ++){
if( (x>>i&1) == 1 && (x>>(i+1)&1 ) == 1) return false;
}
return true;
}
static int count(int x){
int res = 0;
for(int i = 0; i < n; i ++){
if( (x>>i&1) == 1) res++;
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 0 ; i < 1<<n ; i ++){
match[i] = new ArrayList();
if(check(i)){
cnt[i] = count(i);
}
}
for(int i = 0; i < state.size(); i ++){
for(int j = 0; j < state.size(); j ++){
int a = state.get(i);
int b = state.get(j);
if( (a&b) == 0 && check(a | b)) match[i].add(j);
}
}
f[0][0][0] = 1;
for(int i = 1; i <= n +1; i ++){
for(int j = 0; j <= m; j ++){
for(int a = 0; a < state.size(); a ++){
for(int b : match[a]){
int c = cnt[state.get(a)];
if(j >= c) f[i][j][state.get(a)] += f[i - 1][j - c][state.get(b)];
}
}
}
}
System.out.println(f[n+1][m][0]);
}
}


7小时前
import java.util.*;
public class Main{
static int N = 100010, INF = 0x3f3f3f3f;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int w[] = new int[N];
int f[][] = new int[N][3];
f[0][1] = f[0][0] = -INF;
int n = sc.nextInt();
for(int i = 1; i <= n; i ++) w[i] = sc.nextInt();
for(int i = 1; i <= n; i ++) {
f[i][1] = f[i-1][0] + w[i];
f[i][0] = Math.max(f[i-1][0], f[i-1][2] - w[i]);
f[i][2] = Math.max(f[i-1][1], f[i-1][2]);
}
System.out.println(Math.max(f[n][2], f[n][1]) );
}
}


8小时前
import java.util.*;
public class Main{
static int N = 100010;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-- != 0){
int n = sc.nextInt();
int a[] = new int[N];
int f[][] = new int[N][3];
for(int i = 1; i <= n; i ++) a[i] = sc.nextInt();
f[1][0] = 0;
f[1][1] = a[1];
for(int i = 2; i <= n; i ++){
f[i][0] = Math.max(f[i-1][0], f[i-1][1]);
f[i][1] = Math.max(f[i][1], f[i-1][0] + a[i]);
}
System.out.println(Math.max(f[n][0], f[n][1]));
}
}
}
####    一维
f[i] = Math.max(f[i-1], f[i-2] + w[i]);
####    二维状态机
f[i][0] = Math.max(f[i-1][0], f[i-1][1]);
f[i][1] = Math.max(f[i][1], f[i-1][0] + a[i]);


9小时前
/*

f[i, j] 表示在前i项能量石里选，且总时间恰好是j的最大收益；  不选 ： f[i-1, j]；选：f[i-1, j - s] + e-(j-s)*l;
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int C = 1; C <= T; C ++){
int f[] = new int[10010];
Node q[] = new Node[110];
int n = sc.nextInt(), m = 0;
for(int i = 0; i < n; i ++){
int s = sc.nextInt();
int e = sc.nextInt();
int l = sc.nextInt();
m += s;
q[i] = new Node(s, e, l);
}
Arrays.sort(q, 0, n);
Arrays.fill(f, -0x3f3f3f3f);
f[0] = 0;
for(int i = 0; i < n; i ++){
int s = q[i].s , e = q[i].e, l = q[i].l;
for(int j = m; j >= s; j --)
f[j] = Math.max(f[j], f[j - s] + e-(j-s)*l);
}
int res = 0;
for(int i = 0; i <= m; i ++) res = Math.max(res, f[i]);
System.out.println("Case #"+C+": "+res);
}
}
static class Node implements Comparable<Node>{
int s, e, l;
Node(int a, int b, int c){
s = a; e = b; l = c;
}
public int compareTo(Node n){
return  (s * n.l) - (n.s * l);
}
}
}


19小时前
import java.util.*;
public class Main{
static int N = 110, n, m;
static int w[] = new int[N], v[] = new int[N],  f[][] = new int[N][N];
static int e[] = new int[N], ne[] = new int[N], h[] = new int[N],idx;
static void dfs(int u){
for(int i = v[u]; i <= m; i ++) f[u][i] = w[u];
for(int i = h[u]; i != -1; i = ne[i]){
int son = e[i];  //  对于每个子节点都有选和不选两种；
dfs(son);
for(int j = m; j >= v[u]; j --){  //
for(int k = j - v[u]; k >= 0; k --)
f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
Arrays.fill(h, -1);
n = sc.nextInt();
m = sc.nextInt();
int root = 0;
for(int i = 1; i <= n; i ++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
int p = sc.nextInt();
if(p == -1) root = i;
}
dfs(root);
System.out.println(f[root][m]);
}
static void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
}


19小时前
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int mod = 1000000000+7;
int N = 1010;
int f[] = new int[N];
int g[] = new int[N];
Arrays.fill(f, -0x3f3f3f3f);
f[0] = 0;
g[0] = 1;
for(int i = 0; i < n; i ++){
int v = sc.nextInt();
int w = sc.nextInt();
for(int j = m; j >= v; j --){
int max = Math.max(f[j], f[j - v] + w);
int cnt = 0;
if(max == f[j]) cnt = (cnt + g[j]) % mod;
if(max == f[j - v] + w) cnt = (cnt + g[j-v]) % mod;
g[j] = cnt;
f[j] = max;
}
}
int res = 0, max = 0;
for(int i = 0; i <= m; i ++) max = Math.max(max, f[i]);
for(int i = 0; i <= m; i ++){
if(max == f[i]) res = (res + g[i]) % mod;
}
System.out.println(res);
}
}


1天前
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int f[] = new int[1010];
for(int i = 0; i < n; i ++){
int v = sc.nextInt();
int w = sc.nextInt();
int s = sc.nextInt();
if(s == 0){
for(int j = v; j <= m ;j ++) f[j] = Math.max(f[j], f[j - v] + w);
}else{
if(s == -1) s = 1;
for(int k = 1; k < s; k *= 2){
for(int j = m; j >= v*k; j --)
f[j] = Math.max(f[j], f[j - v*k] + w*k);
s -= k;
}
if(s > 0){
for(int j = m ; j >= v*s; j --){
f[j] = Math.max(f[j], f[j - v*s] + w*s);
}
}
}
}
System.out.println(f[m]);
}
}


1天前
import java.util.*;
public class Main{
static int N = 110, M = 25010;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T -- != 0){
int n = sc.nextInt();
int a[] = new int[N];
for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
Arrays.sort(a, 0, n);
int f[] = new int[M];
f[0] = 1;
int res = 0;
for(int i = 0; i < n; i ++){
if(f[a[i]] == 0) res++;
for(int j = a[i]; j <= a[n-1]; j ++){
f[j] += f[j - a[i]];
}
}
System.out.println(res);
}
}
}


1天前
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long f[] = new long[m + 1];
f[0] = 1;
for(int i = 0; i < n; i ++){
int a = sc.nextInt();
for(int j = a; j <= m; j ++){
f[j] += f[j - a];
}
}
System.out.println(f[m]);
}
}


1天前
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
long f[] = new long[3010];
int n = sc.nextInt();
int m = sc.nextInt();
int a[] = new int[20];
f[0] = 1;
for(int i = 1; i <= n; i ++) a[i] = sc.nextInt();
for(int i = 1; i <= n; i ++){
for(int j = a[i]; j <= m; j ++){
f[j] += f[j - a[i]];
}
}
System.out.println(f[m]);
}
}