最大和：用户登录

问题描述

小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 n 个方格, 依次编号 1 至 n, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。

小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格 nn。

当小蓝站在方格 p 上时, 他可以选择跳到 p+1 到 p+D(n−p) 这些方格 中的一个, 其中 D(1)=1, D(x)(x>1) 定义为 x 的最小质因数。

给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。

输入格式

输入的第一行包含一个正整数n 。

第二行包含 n 个整数, 依次表示每个方格中宝物的分值。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

5

1 -2 -1 3 5

样例输出

8

样例输出

最优的跳跃方案为: 1→3→4→5 。

代码：

import java.util.Arrays;
import java.util.Scanner;

public class 最大和 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n  = sc.nextInt();
        int a[] = new int[n+10];
        int b[] = new int[n+10];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 1; i < n+1; i++) {
            b[i] = zhi(n-i);
        }
        int c[] = new int[n+10];
        Arrays.fill(c, -99999999);
        c[1] = a[1];
        for (int i = 1; i < n+1; i++) {
            for (int j = 1+i; j <=b[i]+i; j++) {
                c[j] = Math.max(c[j],a[j]+c[i]);
            }
        }

        System.out.println(c[n]);
    }

    private static int zhi(int m) {
        for (int i = 2; i <=m ; i++) {
            if(m%i==0&&su(i))
                return i;
        }
        return 1;
    }

    private static boolean su(int m) {
        for (int i = 2; i*i <=m; i++) 
            if(m%i==0)
                return false;
        return true;
        
    }

}

翻硬币：用户登录

题目描述

小明正在玩一个"翻硬币"的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo;

如果同时翻转左边的两个硬币，则变为：oooo***oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入描述

两行等长的字符串，分别表示初始状态和要达到的目标状态。

每行的长度<1000。

输出描述

一个整数，表示最小操作步数。

输入输出样例

示例

输入

**********
o****o****

输出

5

运行限制

• 最大运行时间：1s
• 最大运行内存: 64M

代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt=0;
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        for(int i =0;i <s.length-1;i++) {
            if(s[i]!=t[i]) {
                if(s[i+1]=='*') {s[i+1]='o';}
                else {s[i+1]='*';}
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

小船从此逝，江海寄余生