善变的同伴
又到了吃午饭的时间，你和你的同伴刚刚研发出了最新的GSS-483型自动打饭机器人，现在你们正在对机器人进行功能测试。
为了简化问题，我们假设午饭一共有N个菜，对于第i个菜，你和你的同伴对其定义了一个好吃程度（或难吃程度，如果是负数的话……）A[i]，
由于一些技（经）术（费）限制，机器人一次只能接受一个指令：两个数L, R——表示机器人将会去打第L~R一共R-L+1个菜。
本着不浪费的原则，你们决定机器人打上来的菜，含着泪也要都吃完，于是你们希望机器人打的菜的好吃程度之和最大
然而，你善变的同伴希望对机器人进行多次测试（实际上可能是为了多吃到好吃的菜），他想知道机器人打M次菜能达到的最大的好吃程度之和
当然，打过一次的菜是不能再打的，而且你也可以对机器人输入-1, -1，表示一个菜也不打
第一行：N, M
第二行：A[1], A[2], ..., A[N]
输出描述:
一个数字S，表示M次打菜的最大好吃程度之和
7 2
1 2 3 -2 3 -10 3
输出
10
说明
[1 2 3 -2 3] -10 [3]
这道题就是 买股票问题的变体，只能买指定次数k次股票的变体
使用动态规划进行解体：
- 状态量 i菜的位置，能打多少次菜M ,是否打这个菜 （0,1）
dp[i][M][0] = max(dp[i-1][M][0],dp[i-1][M][1]);
dp[i][M][1] = max(dp[i-1][M][1]+A[i],dp[i-1][M-1][0] + A[i])
因为状态只和上一个状态相关
dp_i_0[M]=max(dp_i_0[M], dp_i_1[M])
dp_i_1[M]=max(dp_i_1[M]+A[i], dp_i_0[M-1]+A[i])
import java.util.*;
public class Main {
// 思路 ， 前 m - 1 淘汰
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Integer> nums = new ArrayList<>();
// 将连续的整数和负数进行合并来减少时间复杂度
int x; int p = 0; int q = 0;
long sum = 0;
for (int i=0;i<n;i++){
x = in.nextInt();
if(x > 0){
if(q != 0)
nums.add(q);p += x;q = 0;
}else{
if(p != 0) {
nums.add(p);
}q += x;p = 0;
}
}
if(p != 0){
nums.add(p);
}
if (q != 0){
nums.add(q);
}
if(m > (n+1)/2){
for(int num : nums){
if (num > 0){
sum += (long) num;
}
}
System.out.println(sum);
}else{
int[] dp_i_0 = new int[m+1];
int[] dp_i_1 = new int[m+1];
for (int i=1;i<=m;i++){
dp_i_1[i] = nums.get(0);
}
for (int i=1;i<nums.size();i++){
for(int j=1;j<=m;j++){
dp_i_0[j] = Math.max(dp_i_0[j],dp_i_1[j]);
dp_i_1[j] = Math.max(dp_i_1[j] + nums.get(i),dp_i_0[j-1] + nums.get(i));
}
}
System.out.println(Math.max(dp_i_0[m], dp_i_1[m]));
}
}
}
字符归一化
题目描述
通过键盘输入一串小写字母(a~z)组成的字符串。
请编写一个字符串归一化程序，统计字符串中相同字符出现的次数，并按字典序输出字符及其出现次数。
例如字符串"babcc"归一化后为"a1b2c2"
输入描述:
每个测试用例每行为一个字符串，以'\n'结尾，例如cccddecca
输出描述:
输出压缩后的字符串ac5d2e
dabcab
a2b2c1d1
思路是基数统计
import java.util.*;
public class Main {
// 思路 ， 前 m - 1 淘汰
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 字符串归一化，使用26 字符数组进行统计，基数统计
int[] hash = new int[26];
String line = in.nextLine();
for(char c : line.toCharArray()){
hash[c-'a']++;
}
for (int i=0;i<26;i++){
if (hash[i] > 0){
System.out.print((char) (i+'a'));
System.out.print(hash[i]);
}
}
}
}
字符串排序
月神拿到一个新的数据集，其中每个样本都是一个字符串（长度小于100），样本的的后六位是纯数字，月神需要将所有样本的后六位数字提出来，转换成数字，并排序输出。
月神要实现这样一个很简单的功能确没有时间，作为好朋友的你，一定能解决月神的烦恼，对吧。
输入描述:
每个测试用例的第一行是一个正整数M（1<=M<=100)，表示数据集的样本数目
接下来输入M行，每行是数据集的一个样本，每个样本均是字符串，且后六位是数字字符。
输出描述:
对每个数据集，输出所有样本的后六位构成的数字排序后的结果（每行输出一个样本的结果）
4
abc123455
boyxx213456
cba312456
cdwxa654321
123455
213456
312456
654321
import java.util.*;
public class Main {
// 思路 ， 前 m - 1 淘汰
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 输入数据的个数
int m = in.nextInt();
in.nextLine();
int[] nums = new int[m];
for (int i=0;i<m;i++){
String line = in.nextLine();
String num = line.substring(line.length() - 6);
int x = Integer.parseInt(num);
nums[i] = x;
}
Arrays.sort(nums);
for (int x:nums){
System.out.println(x);
}
}
}
回文字符串
题目描述
最大回文子串是被研究得比较多的一个经典问题。最近月神想到了一个变种，对于一个字符串，如果不要求子串连续，那么一个字符串的最大回文子串的最大长度是多少呢。
输入描述:
每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.
输出描述:
输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）
adbca
3
import java.util.*;
public class Main {
// 思路 ， 前 m - 1 淘汰
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 输入数据的个数
String s = in.nextLine();
// dp[i][j] = dp[i+1][j-1] + 2
int[][] dp = new int[s.length()][s.length()];
for (int i=0;i<s.length();i++){
dp[i][i] = 1;
}
// 这里为了使i+1已经计算过，所以i需要倒置来
for (int i=s.length()-1;i>=0;i--){
for (int j=i+1;j<s.length();j++){
if (s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
System.out.println(dp[0][s.length()-1]);
}
}
latex 爱好者
latex自然是广大研究人员最喜欢使用的科研论文排版工具之一。
月神想在iPhone 上查阅写好的paper，但是无赖iPhone 上没有月神喜欢使用的阅读软件，于是月神也希望像tex老爷爷Donald Knuth那样自己动手do it yourself一个。
在DIY这个阅读软件的过程中，月神碰到一个问题，已知iPhone屏幕的高为H，宽为W，若字体大小为S(假设为方形），则一行可放W / S(取整数部分）个文字，一屏最多可放H / S （取整数部分）行文字。
已知一篇paper有N个段落，每个段落的文字数目由a1, a2, a3,...., an表示，月神希望排版的页数不多于P页（一屏显示一页），那么月神最多可使用多大的字体呢？
1 <= W, H, ai <= 1000
1 <= P <= 1000000
输入描述:
每个测试用例的输入包含两行。
第一行输入N,P,H,W
第二行输入N个数a1,a2,a3,...,an表示每个段落的文字个数。
输出描述:
对于每个测试用例，输出最大允许的字符大小S
1 10 4 3 10 2 10 4 3 10 10
3 2
数学解法
import java.util.*;
public class Main {
// 思路 ，
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 输入数据的个数
while (in.hasNext()){
int n = in.nextInt();
int p = in.nextInt();
int h = in.nextInt();
int w = in.nextInt();
long sum = 0;
int[] f = new int[n];
for (int i=0;i<n;i++){
f[i] = in.nextInt();
sum += f[i];
}
long total = (p * h * w) / sum;
int s = (int)Math.sqrt(total);
int th = 0;
for (int i=0;i<n;i++){
th += (f[i] * s)/w;
if((f[i] * s)% w != 0){
th = th+1;
}
}
if(th > p * (h/s)){
System.out.println(s-1);
}else {
System.out.println(s);
}
}
}
}
采用二分法进行ac
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int n = sc.nextInt();
static int p = sc.nextInt();
static int h = sc.nextInt();
static int w = sc.nextInt();
static int[] numPerN = new int[n];
public static void main(String[] args) {
for (int i = 0; i < n; i++) {
numPerN[i] = sc.nextInt();
}
int l = 1;
int r = Math.min(h, w);//字号最大为行宽和列高中较小的一个
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (isOk(mid)) {
l = mid;
} else {
r = mid;
}
}
if (isOk(r)) {
System.out.println(r);
} else {
System.out.println(l);
}
}
public static boolean isOk(int size) {
int totalHang = 0;// 一共有多少行
int preHang = w / size;// 每行有多少字
for (int i = 0; i < n; i++) {
int temp = numPerN[i] / preHang;// 每一段要多少行
if (numPerN[i] % preHang != 0) {
temp++;
}
totalHang += temp;
}
int perYe = h / size;// 每一页有多少行
int totalYe = totalHang / perYe;// 一共有多少页
if (totalHang % perYe != 0) {
totalYe++;
}
if (totalYe <= p) {
return true;
} else {
return false;
}
}
}
网友评论