目录

898. 数字三角形 - 线性dp

1、只求最大路径值 dp 

2、求最大路径值+打印最大路径

L2-041 插松枝 - 大模拟 + 栈 （19 / 25）未ac

L2-042 老板的作息表 - 差分（17 / 25）未ac

1、差分java喜闻乐见的tle 爪哇不配写pta

2、按字典序排序

898. 数字三角形 - 线性dp

活动 - AcWing

题目：

1、只求最大路径值 dp 

import java.util.*;class Main
{static int N=510;static int[][] f=new int[N][N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();for(int i=1;i<=n;i++) //枚举层数for(int j=1;j<=i;j++) f[i][j]=sc.nextInt();for(int i=n-1;i>=1;i--) //从底向上for(int j=1;j<=i;j++)f[i][j]+=Math.max(f[i+1][j],f[i+1][j+1]);System.out.print(f[1][1]);}
}

2、求最大路径值+打印最大路径

import java.util.*;class Main
{static int N=510;static int[][] f=new int[N][N],a=new int[N][N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] res=new int[N];Map,List> mp=new HashMap<>();int cnt=0;for(int i=1;i<=n;i++) //枚举层数for(int j=1;j<=i;j++)a[i][j]=f[i][j]=sc.nextInt();for(int i=n-1;i>=1;i--) //从底向上{for(int j=1;j<=i;j++){int t=Math.max(f[i+1][j],f[i+1][j+1]);List list1=new ArrayList<>();list1.add(i);list1.add(j);if(t==f[i+1][j]){List list2=new ArrayList<>();list2.add(i+1);list2.add(j);mp.put(list1,list2);}else {List list2=new ArrayList<>();list2.add(i+1);list2.add(j+1);mp.put(list1,list2);}f[i][j]+=t; }}int nx=1,ny=1;while(nx!=n&&ny!=n){res[cnt++]=a[nx][ny];List tt=new ArrayList<>();tt.add(nx);tt.add(ny);List t1=mp.get(tt);nx=t1.get(0);ny=t1.get(1);}res[cnt]=a[nx][ny]; System.out.print(f[1][1]);System.out.print("[");for(int i=0;i");System.out.print(res[i]);}System.out.println("]");}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

L2-041 插松枝 - 大模拟 + 栈 （19 / 25）未ac

PTA | 程序设计类实验辅助教学平台

改了一下午不知道哪错了可恶！！！

思路：

• 用st数组记录每一根推进器上的松针是否被使用（插上/放进盒子）
• 盒子里因为是叠放，所以用栈实现（先进后出），盒子里的松针优先插
• 然后取出推进器上未被使用的松针，如果比当前松枝上插的松针短，则插入
• 否则放入盒子中，如果盒子已满，则完成一根成品松枝，输出松枝
• 如果盒子和推进器上都没有，则结束工作

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();int[] a=new int[n];int[] st=new int[n];int nums=0;for(int i=0;i stk=new LinkedList<>();while(true){if(nums==n&&stk.isEmpty()) break; //如果推送器空了且盒子为空int[] res=new int[n];int cnt=0,pre=110;while(!stk.isEmpty()) //在小盒子里取松针{int t=stk.peek();if(t>pre) break;res[cnt++]=t;nums++;pre=stk.pop();if(cnt==k) break;}for(int i=0;i

import java.util.*;class Main
{public static int work(String s){String[] tt=s.split(":");int hh=Integer.parseInt(tt[0]);int mm=Integer.parseInt(tt[1]);int ss=Integer.parseInt(tt[2]);return hh*3600+mm*60+ss;}public static String convert(int x){String res="";int hh=x/3600;if(hh<10) res+="0";res+=String.valueOf(hh);res+=":";x-=hh*3600;int mm=x/60;if(mm<10) res+="0";res+=String.valueOf(mm);res+=":";x-=mm*60;if(x<10) res+="0";res+=String.valueOf(x);return res;}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();String tun=sc.nextLine();int[] b=new int[86401];while(n-->0){String[] s=sc.nextLine().split(" - ");int l=work(s[0]);int r=work(s[1]);b[l]++;b[r]--;}for(int i=1;i<=86400;i++) b[i]+=b[i-1];List res=new ArrayList<>();int l=90000,r=-1;for(int i=0;i<86400-1;i++) {if(b[i]==0){l=Math.min(l,i);r=Math.max(r,i+1);}else if(l!=90000&&r!=-1){res.add(new PII(l,r));l=90000;r=-1;}}if(l!=90000&&r!=-1) res.add(new PII(l,r));for(var p:res)System.out.println(convert(p.x)+" - "+convert(p.y));}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

#include 
using namespace std;
int n;
int get(string s)
{return ((s[0]-'0')*10+(s[1]-'0'))*3600+((s[3]-'0')*10+s[4]-'0')*60+(s[6]-'0')*10+s[7]-'0';
}
string func(int x)
{string res;int h=x/3600;int r=x-h*3600;int m=r/60;int s=r-m*60;res+=to_string(h/10)+to_string(h%10)+":"+to_string(m/10)+to_string(m%10)+":"+to_string(s/10)+to_string(s%10);return res;
}
const int N=2e5+10;
int s[N];
int main()
{cin>>n;getchar();for(int i=1;i<=n;i++){string str;getline(cin,str);string s1=str.substr(0,8),s2=str.substr(11);int l=get(s1),r=get(s2);s[l]++,s[r]--;}vector>v;for(int i=1;i<=24*60*60;i++)s[i]+=s[i-1];int l=0x3f3f3f3f,r=-1;for(int i=0;i<24*60*60-1;i++){if(s[i]==0){l=min(l,i),r=max(r,i+1);}else if(l!=0x3f3f3f3f&&r!=-1)v.push_back({l,r}),l=0x3f3f3f3f,r=-1;}if(l!=0x3f3f3f3f&&r!=-1)v.push_back({l,r});for(auto x:v){cout<

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();String tun=sc.nextLine();String[] s=new String[n];for(int i=0;i