某易

[编程题] 瞌睡

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

输入描述:

第一行 n, k (1 <= n, k <= 105) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数，a1, a2, ... , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数，t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。

输出描述:

小易这堂课听到的知识点的最大兴趣值。

输入例子1:

6 3
1 3 5 2 5 4
1 1 0 1 0 0

输出例子1:

 1 import java.util.*;
 2 
 3 
 4 public class Main {
 5    public static void main(String[] args) 
 6    {
 7         Scanner sc=new Scanner(System.in);
 8         int n=sc.nextInt();
 9         int k=sc.nextInt();
10         int[] mark=new int[n];
11         long[] max=new long[n];
12         short[] iswake=new short[n];
13         for (int i = 0; i < mark.length; i++) {
14             mark[i]=sc.nextInt();
15         }
16         for (int i = 0; i < mark.length; i++) {
17             iswake[i]=sc.nextShort();
18          }
19         long fix=0;
20         for (int i = 0; i < iswake.length; i++) {
21             if (iswake[i]==1) {
22                 fix=fix+mark[i];
23                 mark[i]=0;//将加过的兴趣值的改成0
24             }
25         }
26         for (int i = 0; i < n; i++) {
27             max[i]=fix;
28         }
29         for (int i = 0; i < iswake.length; i++) {
30             if (iswake[i]==0) {
31                 if (i+k>n) {
32                     for (int j = i; j < n; j++) {
33                     
34                         max[i]=max[i]+mark[j];
35                     }
36                     break;//后面的肯定小于第一个故不需要继续计算
37                     
38                 }else {
39                     for (int j = i; j < i+k; j++) {
40                         
41                         max[i]=max[i]+mark[j];
42                     }
43                 }
44                 
45             }
46             
47         }
48         
49         Arrays.sort(max);
50         System.out.println(max[max.length-1]);
51       
52     }
53 
54 }
55  
56

回文字符串

回文字符串，指的是形式如同"abcba"或是"abccba“形式的字符串。

那么如何在一串给定的字符串中寻找其中最长的回文子串呢？

 1 package uestc;
 2 
 3 public class Main {
 4 
 5             public static void main(String[] args) {
 6                 String s = "xccxbdc";
 7                 String solu = longestPalindrome1(s);
 8                 System.out.println(solu);
 9 
10             }
11             public static String longestPalindrome(String s) {
12                 int len = s.length();
13                 int maxLen = 0;
14                 String res = null;
15                 boolean[][] dp = new boolean[len][len];
16                 for(int i = len - 1;i >= 0;i--){
17                     for(int j = i;j < len;j++){
18                         dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1] == true);
19                         //（1）当前遍历到的子串i~j是否是回文子串取决于i+1~j-1，也就是i~j中间的子串是否是回文并且s[i]是否等于s[j]；
20                         //（2）dp[i][j]是为true则意味着i~j是回文子串，则在下面判断后对res进行更新；如果为false，则该子串不是回文子串，开始遍历下一个子串。
21                         if(dp[i][j] == true && (res == null || j - i + 1 > maxLen)){
22                             //如果该子串长度更长，则更新res
23                             res = s.substring(i, j+1);
24                             maxLen = res.length();
25                         }
26                     }
27                 }
28            
29                 return res;
30             }
31             private static int start;
32             private static int maxLength;    
33             public static String longestPalindrome1(String s) //这是
34             {        
35                 if(s.length()<2)            
36                       return s;        
37                 for(int i=0;i<s.length()-1;i++)
38                 {       //遍历整个数组，寻找回文子串最中间的字符，如果回文子串是奇数长度，那么最中间有一个字符；否则有两个字符
39                          extendPali(s,i,i);
40                         
41                          extendPali(s,i,i+1);    
42                         
43                 }   
44                 return s.substring(start,start+maxLength);    
45                      
46             }   
47             public static void extendPali(String s,int i,int j)
48             {     
49                 while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j))
50                 {            
51                               i--;  //如果满足括号里的条件，则继续向两边扩展        
52                               j++;       
53                 }       
54                 if(maxLength<j-i-1){ //更新最大长度的值           
55                     start=i+1;            
56                     maxLength=j-i-1;        
57                 }  
58             }
           }