# AP325 補救計畫(II)
作者:欉恩祁
因為我跟竑誠在APCS被其他人給電爛了，所以決定來寫TCIRC的神奇題目來補救。
[>>Part I](https://hackmd.io/@r1cky/H1n-nQf_Y)
---
## d061~d080
### d061 監看華山練功場
解法:greedy
```Java=
import java.io.*;
import java.util.*;
public class d061 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,idx=0,cnt,ans;
public static seg p=null;
public static boolean so=true;
public static void main(String[] args) throws Exception{
final int n=orz();
final int x=orz();
final int y=orz();
seg[] s=new seg[n];
for(int i=0;i<n;i++) {
s[i]=new seg(orz(),orz());
}
Arrays.sort(s,new Comparator<seg>() {
public int compare(seg f,seg s) {
return f.l-s.l;
}
});
PriorityQueue<seg> pq=new PriorityQueue<>(new Comparator<seg>() {
public int compare(seg f,seg s) {
return f.r-s.r;
}
});
cnt=x+1;
all:
while(cnt<y) {
while(idx<n&&s[idx].l<=cnt) {
pq.offer(s[idx]);
idx++;
}
if(pq.isEmpty()) {
so=false;
break all;
}
while(!pq.isEmpty())p=pq.poll();
cnt=p.r;
ans++;
}
if(so) {
System.out.println(ans);
}
else {
System.out.println(-1);
}
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class seg{
int l,r;
seg(int a,int b){
l=a;
r=b;
}
}
```
---
### d064 反序數量
解法:BIT
```Java=
import java.util.*;
import java.io.*;
public class d064 {
public static int[] bit=new int[1000005];
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] read=br.readLine().split(" ");
int t=Integer.parseInt(read[0]);
long out=0;
int a;
read=br.readLine().split(" ");
for(int i=0;i<1000005;i++)bit[i]=0;
for(int i=t-1;i>=0;i--) {
a=Integer.parseInt(read[i]);
out+=sum(a);
update(a+1);
}
System.out.println(out);
}
public static void update(int x) {
for(int i=x;i<1000005;i+=i&(-i)) {
bit[i]+=1;
}
}
public static int sum(int x) {
int r=0;
for(int i=x;i>0;i-=i&(-i)) {
r+=bit[i];
}
return r;
}
}
```
---
### d065 大樓外牆廣告
解法:monotone stack(感謝電神thanksone、宗翰提供意見!)
```Java=
import java.io.*;
import java.util.*;
public class d065 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long mx=0;
public static void main(String[] args) throws Exception{
String[] r=br.readLine().split(" ");
final int n=Integer.parseInt(r[0]);
int id;
long in;
p po;
Stack<p> a=new Stack<>();
int[] h=new int[n];
r=br.readLine().split(" ");
for(int i=0;i<n;i++)h[i]=Integer.parseInt(r[i]);
for(int i=0;i<n;i++) {
in=h[i];
id=i;
while(a.size()!=0) {
po=a.pop();
if(po.h<in) {
a.push(po);
break;
}
if(po.idx<id)id=(int)po.idx;
mx=Math.max((i-po.idx)*po.h,mx);
}
a.push(new p(id,in));
}
while(a.size()!=0) {
po=a.pop();
mx=Math.max((n-po.idx)*po.h,mx);
}
System.out.println(mx);
}
}
class p{
long idx,h;
p(long a,long b){
idx=a;
h=b;
}
}
```
---
### d066 小朋友上樓梯最小成本
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d066 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int[] p=new int[n];
int[] dp=new int[n+1];
for(int i=0;i<n;i++) {
p[i]=orz();
}
dp[0]=0;
dp[1]=p[0];
for(int i=2;i<=n;i++) {
dp[i]=Math.min(dp[i-1],dp[i-2])+p[i-1];
}
System.out.println(dp[n]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d067 不連續的表演酬勞
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d067 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int[] p=new int[n];
int[] dp=new int[n+1];
for(int i=0;i<n;i++) {
p[i]=orz();
}
dp[0]=0;
dp[1]=p[0];
dp[2]=p[1];
for(int i=3;i<=n;i++) {
dp[i]=Math.max(dp[i-3],dp[i-2])+p[i-1];
}
System.out.println(Math.max(dp[n-1],dp[n]));
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d068 最小監控鄰居的成本
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d068 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static int[][] dp=new int[100005][3];
public static int[] cost=new int[100005];
public static void main(String[] args) throws Exception{
final int n=orz();
for(int i=1;i<=n;i++) {
cost[i]=orz();
}
dp[0][0]=0;
dp[0][1]=1<<30;
dp[0][2]=cost[1];
cost[n+1]=cost[n];
for(int i=1;i<=n;i++) {
dp[i][0]=dp[i-1][1];
dp[i][1]=dp[i-1][2];
dp[i][2]=Math.min(dp[i-1][0],Math.min(dp[i-1][1],dp[i-1][2]))+cost[i+1];
}
System.out.println(Math.min(dp[n][0],Math.min(dp[n][1],dp[n][2])));
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d069 方格棋盤路線
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d069 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static int[][] dp=new int[205][205];
public static int[][] mp=new int[205][205];
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
mp[i][j]=orz();
}
}
dp[0][0]=mp[0][0];
for(int i=1;i<m;i++) {
dp[0][i]=dp[0][i-1]+mp[0][i];
}
for(int i=1;i<n;i++) {
dp[i][0]=dp[i-1][0]+mp[i][0];
}
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+mp[i][j];
}
}
System.out.println(dp[n-1][m-1]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d070 LCS
解法:LCS
```Java=
import java.io.*;
import java.util.*;
public class d070 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static int[][] dp=new int[505][505];
public static void main(String[] args) throws Exception{
String a=br.readLine();
String b=br.readLine();
final int m=a.length()+1;
final int n=b.length()+1;
for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
if(a.charAt(i-1)==b.charAt(j-1)) {
dp[i][j]=dp[i-1][j-1]+1;
}
else {
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
System.out.println(dp[m-1][n-1]);
}
}
```
---
### d071 大賣場免費大搬家
解法:背包低批
```Java=
import java.io.*;
import java.util.*;
public class d071 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
final int l=orz();
int[] dp=new int[l+1];
Arrays.fill(dp,0);
int[] w=new int[n];
int[] v=new int[n];
for(int i=0;i<n;i++)w[i]=orz();
for(int i=0;i<n;i++)v[i]=orz();
for(int i=0;i<n;i++) {
for(int j=l;j>=w[i];j--) {
dp[j]=Math.max(dp[j-w[i]]+v[i],dp[j]);
}
}
System.out.println(dp[l]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d072 闖關二選一
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d072 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static int[][] dp=new int[100005][2];
public static int[][] mp=new int[100005][2];
public static void main(String[] args) throws Exception{
final int n=orz();
final int t=orz();
for(int i=1;i<=n;i++) {
mp[i][0]=orz();
mp[i][1]=orz();
}
mp[0][0]=mp[0][1]=t;
for(int i=1;i<=n;i++) {
dp[i][0]=Math.min(dp[i-1][0]+Math.abs(mp[i][0]-mp[i-1][0]),dp[i-1][1]+Math.abs(mp[i][0]-mp[i-1][1]));
dp[i][1]=Math.min(dp[i-1][0]+Math.abs(mp[i][1]-mp[i-1][0]),dp[i-1][1]+Math.abs(mp[i][1]-mp[i-1][1]));
}
System.out.println(Math.min(dp[n][0],dp[n][1]));
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d073 二維最大子矩陣
解法:一軸DP另一軸暴力、前綴和
```Java=
import java.io.*;
public class d073 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int max=0,id=0;
public static boolean neg;
public static int[] dp=new int[2];
public static int[][] msum=new int[205][205];
public static void main(String[] args) throws Exception{
String[] r=br.readLine().split(" ");
final int n=Integer.parseInt(r[0]);
final int m=Integer.parseInt(r[1]);
for(int i=0;i<n;i++) {
r=br.readLine().split(" ");
for(int j=1;j<=m;j++) {
msum[i][j]=msum[i][j-1]+Integer.parseInt(r[j-1]);
}
}
for(int i=0;i<m;i++) {
for(int j=i+1;j<=m;j++) {
id=0;
dp[0]=dp[1]=0;
for(int k=0;k<n;k++) {
dp[id^1]=Math.max(dp[id],0)+msum[k][j]-msum[k][i];
max=Math.max(max,dp[id^1]);
id^=1;
}
}
}
System.out.println(max);
}
}
```
---
### d074 Local alignment
解法:DP、生物學(?)
```Java=
import java.io.*;
public class d074 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int max=0;
public static int[][] dp=new int[505][505];
public static void main(String[] args) throws Exception{
String a=br.readLine();
String b=br.readLine();
final int m=a.length()+1;
final int n=b.length()+1;
for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
if(a.charAt(i-1)==b.charAt(j-1)) {
dp[i][j]=dp[i-1][j-1]+8;
if(dp[i][j]>max)max=dp[i][j];
}
else {
dp[i][j]=Math.max(dp[i-1][j-1]-5,Math.max(dp[i-1][j]-3,dp[i][j-1]-3));
if(dp[i][j]>max)max=dp[i][j];
if(dp[i][j]<0)dp[i][j]=0;
}
}
}
System.out.println(max);
}
}
```
---
### d076 Catalan number
解法:Catalan number
```Java=
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class d076 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
final int n=Integer.parseInt(in[0]);
BigInteger a=new BigInteger("1");
BigInteger b=new BigInteger("1");
BigInteger p=new BigInteger("1000000009");
for(int i=1;i<=n+1;i++) {
a=a.multiply(new BigInteger(Integer.toString(i)));
}
for(int i=n+1;i<=2*n;i++) {
b=b.multiply(new BigInteger(Integer.toString(i)));
}
System.out.println((b.divide(a)).mod(p));
}
}
```
---
### d077 周伯通的基地台
解法:博愛排隊
```Java=
import java.io.*;
import java.util.*;
public class d077 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
final int k=orz();
int in;
dp p;
PriorityQueue<dp> pq=new PriorityQueue<>(new Comparator<dp>() {
public int compare(dp f,dp s) {
return f.cost-s.cost;
}
});
pq.offer(new dp(-1,0));
for(int i=0;i<n;i++) {
in=orz();
while(!pq.isEmpty()) {
p=pq.poll();
if(p.mx+1>=i-k) {
pq.offer(p);
pq.offer(new dp(i+k,p.cost+in));
break;
}
}
}
while(!pq.isEmpty()) {
p=pq.poll();
if(p.mx+1>=n) {
System.out.println(p.cost);
break;
}
}
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class dp{
int mx,cost;
dp(int a,int b){
mx=a;
cost=b;
}
}
```
---
### d078 一覽衆山小
解法:LCS
```Java=
import java.io.*;
import java.util.*;
public class d078 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int in,bis;
ArrayList<Integer> a=new ArrayList<Integer>();
for(int i=0;i<n;i++) {
in=orz();
bis=Collections.binarySearch(a,in);
if(bis<0) {
bis=bis*-1-1;
if(bis==a.size()) {
a.add(in);
}
else {
a.set(bis,in);
}
}
}
System.out.println(a.size());
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d079 切棍子
解法:DP、遞迴
```Java=
import java.io.*;
import java.util.*;
public class d079 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static int[][] dp=new int[205][205];
public static int[] mp=new int[205];
public static void main(String[] args) throws Exception{
final int n=orz();
final int l=orz();
mp[0]=0;
mp[n+1]=l;
for(int i=1;i<=n;i++) {
mp[i]=orz();
}
System.out.println(query(1,n));
}
public static int query(int l,int r) {
if(l>r)return 0;
if(dp[l][r]!=0) return dp[l][r];
if(l==r) {
dp[l][r]=mp[l+1]-mp[l-1];
return dp[l][r];
}
int mn=1<<30;
for(int i=l;i<=r;i++) {
mn=Math.min(mn,query(l,i-1)+query(i+1,r)+mp[r+1]-mp[l-1]);
}
dp[l][r]=mn;
return dp[l][r];
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d080 階梯數字
解法:遞迴
```Java=
import java.util.*;
import java.io.*;
public class d080 {
public static int out=0;
public static byte end=0;
public static byte[] lim;
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] read=br.readLine().split(" ");
end=(byte)read[0].length();
long num=Long.parseLong(read[0]);
int c=0;
lim=new byte[100];
for(int i=1;i<=end;i++) {
lim[i]=(byte)(num/(long)(Math.pow(10,end-i))%10);
}
find((byte)0,(byte)0,true);
System.out.println(out-1);
}
public static void find(byte x,byte cl,boolean b) {
if(cl==end) {
out++;
return;
}
else {
cl++;
for(byte i=x;i<10;i++) {
if(b) {
if(i<lim[cl]) {
find(i,(byte)cl,false);
}
else if(i==lim[cl]) {
find(i,(byte)cl,true);
}
else return;
}
else find(i,(byte)cl,false);
}
}
}
}
```
---
## d081~d100
### d081 Hyper-cube path
解法:DP
```Java=
import java.io.*;
public class d081 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static int[] dp=new int[1<<20];
public static void main(String[] args) throws Exception{
final int n=orz();
int mx,d,lowbit;
for(int i=0;i<(1<<n);i++) {
d=i;
mx=0;
while(d!=0) {
lowbit=d&(-d);
d-=lowbit;
mx=Math.max(mx,dp[i-lowbit]);
}
dp[i]=mx+orz();
}
System.out.println(dp[(1<<n)-1]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d082 刪除邊界
解法:DP、遞迴
```Java=
import java.io.*;
import java.util.*;
public class d082 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt,c;
public static int[][][][] dp=new int[35][35][35][35];
public static boolean[][] mp=new boolean[35][35];
public static void main(String[] args) throws Exception{
final int m=orz();
final int n=orz();
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
mp[i][j]=(orz()==1)?true:false;
}
}
for(int i=0;i<30;i++)for(int j=0;j<30;j++)for(int k=0;k<30;k++)for(int l=0;l<30;l++)dp[i][j][k][l]=-1;
System.out.println(q(0,m-1,0,n-1));
}
public static int q(int lx,int rx,int ly,int ry) {
if(lx==rx||ly==ry)return 0;
if(dp[lx][rx][ly][ry]!=-1)return dp[lx][rx][ly][ry];
int min=1<<30;
min=Math.min(q(lx+1,rx,ly,ry)+mn(lx,lx,ly,ry),min);
min=Math.min(q(lx,rx-1,ly,ry)+mn(rx,rx,ly,ry),min);
min=Math.min(q(lx,rx,ly+1,ry)+mn(lx,rx,ly,ly),min);
min=Math.min(q(lx,rx,ly,ry-1)+mn(lx,rx,ry,ry),min);
dp[lx][rx][ly][ry]=min;
return dp[lx][rx][ly][ry];
}
public static int mn(int lx,int rx,int ly,int ry) {
if(dp[lx][rx][ly][ry]!=-1)return dp[lx][rx][ly][ry];
cnt=c=0;
for(int i=lx;i<=rx;i++) {
for(int j=ly;j<=ry;j++) {
if(mp[i][j])cnt++;
else c++;
}
}
dp[lx][rx][ly][ry]=Math.min(c,cnt);
return dp[lx][rx][ly][ry];
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d083 文無第一武無第二
解法:單調序列、LIS、二分搜
```Java=
import java.io.*;
import java.util.*;
public class d083 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,ans=0;
public static int[][] in;
public static void main(String[] args) throws Exception{
final int n=orz();
int l,r,m,preval;
ArrayList<pair> a=new ArrayList<>();
a.add(new pair(-2,0));
a.add(new pair(Integer.MAX_VALUE,Integer.MAX_VALUE));
in=new int[n][3];
for(int i=0;i<3;i++) {
for(int j=0;j<n;j++)in[j][i]=orz();
}
Arrays.sort(in,new Comparator<int[]>() {
public int compare(int[] f,int[] s) {
if(f[1]!=s[1])return (s[1]-f[1]);
return (f[2]-s[2]);
}
});
for(int i=0;i<n;i++) {
l=0;
r=a.size()-1;
while(l!=r) {
m=(l+r+1)/2;
if(a.get(m).idx>in[i][2]) {
r=m-1;
}
else {
l=m;
}
}
preval=in[i][0]+a.get(l).val;
l=0;
r=a.size()-1;
while(l!=r) {
m=(l+r)/2;
if(a.get(m).val>=preval) {
r=m;
}
else {
l=m+1;
}
}
if(a.get(l).idx<=in[i][2])continue;
a.add(l,new pair(in[i][2],preval));
l--;
while(a.get(l).idx>=in[i][2]) {
a.remove(l);
l--;
}
ans=Math.max(ans,preval);
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int idx,val;
pair(int a,int b){
idx=a;
val=b;
}
}
```
---
### d084 楊鐵心做 1 休 K
解法:Queue、greedy
```Java=
import java.io.*;
import java.util.*;
public class d084 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,in,p,max;
public static void main(String[] args) throws Exception{
final int n=orz();
final int k=orz();
Queue<Integer> q=new LinkedList<>();
for(int i=0;i<k;i++) {
q.offer(0);
}
for(int i=0;i<n;i++) {
in=orz();
q.offer(max+in);
p=q.poll();
if(p>max)max=p;
}
while(!q.isEmpty()) {
p=q.poll();
if(p>max)max=p;
}
System.out.println(max);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d085 K次買賣 O(nk)
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d085 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,x=0,in;
public static long[][][] dp=new long[2][205][2];
public static void main(String[] args) throws Exception{
final int n=orz();
final int k=orz();
dp[0][0][1]=-(1<<30);
dp[1][0][1]=-(1<<30);
for(int i=0;i<n;i++) {
in=orz();
for(int j=0;j<k;j++) {
dp[x^1][j][1]=Math.max(dp[x][j][0]-in,dp[x][j][1]);
dp[x^1][j+1][0]=Math.max(dp[x][j][1]+in,dp[x][j+1][0]);
}
x^=1;
}
System.out.println(dp[x][k][0]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d086 矩陣乘法鏈
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d086 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static int[][] dp=new int[205][205];
public static int[] in=new int[205];
public static void main(String[] args) throws Exception{
final int n=orz();
for(int i=0;i<=n;i++)in[i]=orz();
System.out.println(rec(0,n-1));
}
public static int rec(int l,int r) {
if(dp[l][r]!=0)return dp[l][r];
if(l>=r)return 0;
int mn=1<<30;
for(int i=l;i<r;i++) {
mn=Math.min(mn,rec(l,i)+rec(i+1,r)+in[l]*in[i+1]*in[r+1]);
}
dp[l][r]=mn;
return mn;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d087 直升機抓寶
解法:LIS
```Java=
import java.io.*;
import java.util.*;
public class d087 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int l,r,m,a=0,b=0;
ArrayList<Integer> lis=new ArrayList<>();
lis.add(-1);
lis.add(1<<30);
for(int i=0;i<n;i++) {
a=orz();
b=orz();
l=0;
r=lis.size()-1;
while(l!=r) {
m=(l+r)/2;
if(lis.get(m)<=a) {
l=m+1;
}
else {
r=m;
}
}
lis.add(l,a);
l--;
r=lis.size()-1;
while(l!=r) {
m=(l+r)/2;
if(lis.get(m)<=b) {
l=m+1;
}
else {
r=m;
}
}
if(l!=lis.size()-1)lis.remove(l);
}
System.out.println(lis.size()-2);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
//參考:https://emanlaicepsa.github.io/2020/12/07/0-20/
```
---
### d088 隔離採礦
解法:Monotone stack、DP、Priority queue
```Java=
import java.io.*;
import java.util.*;
import java.math.*;
public class d088 {
public static int re,ret,mx,ans,idx=0;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int[] h=new int[1000005];
public static void main(String[] args) throws Exception{
final int n=orz();
int v;
pii p;
pii[] a=new pii[1000005];
a[0]=new pii(1<<30,0);
PriorityQueue<pii> pq=new PriorityQueue<>(new Comparator<pii>() {
public int compare(pii f,pii s) {
return f.h-s.h;
}
});
for(int i=0;i<n;i++)h[i]=orz();
for(int i=0;i<n;i++) {
v=orz();
mx=-1;
while(!pq.isEmpty()) {
p=pq.poll();
if(p.h>=h[i]) {
pq.offer(p);
break;
}
mx=Math.max(mx,p.v);
}
while(a[idx].h<=h[i]) {
mx=Math.max(mx,a[idx].v);
idx--;
}
mx=Math.max(mx,a[idx].v);
pq.offer(new pii(h[i],a[idx].v+v));
if(a[idx].v<mx)a[++idx]=new pii(h[i],mx);
}
for(int i=0;i<=idx;i++) {
ans=Math.max(a[i].v,ans);
}
while(!pq.isEmpty()) {
ans=Math.max(pq.poll().v,ans);
}
System.out.println(ans);
}
public static int orz()throws Exception {
ret=0;
re=br.read();
while(re>47&&re<58) {
ret*=10;
ret+=(re&15);
re=br.read();
}
return ret;
}
}
class pii{
int h,v;
pii(int a,int b){
h=a;
v=b;
}
}
```
---
### d089 貨郎問題
解法:位元低批
```Java=
import java.io.*;
import java.util.*;
public class d089 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static final int inf=1<<30;
public static int[][] cost=new int[16][16];
public static int[][] dp=new int[1<<16][16];
public static void main(String[] args) throws Exception{
final int n=orz();
orz();
int mn;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cost[i][j]=orz();
for(int i=1;i<n;i++)dp[0][i]=inf;
for(int i=1;i<(1<<n);i++) {
for(int j=0;j<n;j++) {
if((i&(1<<j))==0) {
dp[i][j]=inf;
}
else {
mn=inf;
for(int k=0;k<n;k++) {
mn=Math.min(mn,dp[i-(1<<j)][k]+cost[k][j]);
}
dp[i][j]=mn;
}
}
}
System.out.println(dp[(1<<n)-1][0]);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d090 機器人走棋盤
解法:bfs
```Java=
import java.io.*;
import java.util.*;
public class d090 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt=0,ans=0;
static ArrayList<ArrayList<Integer>> a=new ArrayList<>();
static boolean[] vis=new boolean[105];
public static void main(String[] args) throws Exception{
new Thread(null,new d090(),"",1<<26).start();
}
public void run() {
final int n=orz();
final int m=orz();
final int s=orz();
int p,d=1;
for(int i=0;i<n;i++)a.add(new ArrayList<Integer>());
for(int i=0;i<m;i++) {
a.get(orz()).add(orz());
}
Queue<Integer> q=new LinkedList<>();
vis[s]=true;
q.offer(s);
q.offer(-1);
while(!q.isEmpty()) {
p=q.poll();
if(p==-1) {
d++;
if(!q.isEmpty())q.offer(-1);
continue;
}
for(int i:a.get(p)) {
if(!vis[i]) {
cnt++;
ans+=d;
vis[i]=true;
q.offer(i);
}
}
}
System.out.println(cnt);
System.out.println(ans);
}
static int orz(){
ret=0;
try {
r=br.read();
} catch (IOException e) {
e.printStackTrace();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {
r=br.read();
} catch (IOException e) {
e.printStackTrace();
}
}
return ret;
}
}
```
---
### d091 開車蒐集寶物
解法:dfs
```Java=
import java.io.*;
import java.util.*;
public class d091 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt,ans=0;
static ArrayList<ArrayList<Integer>> a=new ArrayList<>();
static boolean[] vis=new boolean[50005];
static int[] v=new int[50005];
public static void main(String[] args) throws Exception{
new Thread(null,new d091(),"",1<<26).start();
}
public void run() {
final int n=orz();
final int m=orz();
int x,y;
for(int i=0;i<n;i++) {
a.add(new ArrayList<Integer>());
v[i]=orz();
}
for(int i=0;i<m;i++) {
x=orz();
y=orz();
a.get(x).add(y);
a.get(y).add(x);
}
for(int i=0;i<n;i++) {
cnt=0;
dfs(i);
if(ans<cnt)ans=cnt;
}
System.out.println(ans);
}
static void dfs(int x) {
if(vis[x])return;
cnt+=v[x];
vis[x]=true;
for(int i:a.get(x)) {
dfs(i);
}
}
static int orz(){
ret=0;
try {
r=br.read();
} catch (IOException e) {
e.printStackTrace();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {
r=br.read();
} catch (IOException e) {
e.printStackTrace();
}
}
return ret;
}
}
```
---
### d092 機器人走棋盤
解法:dfs
```Java=
import java.util.*;
import java.io.*;
public class d092 {
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] read=br.readLine().split(" ");
int xr=Integer.parseInt(read[0]);
int yr=Integer.parseInt(read[1]);
int[][] mp=new int[xr+2][yr+2];
final int max=200000000;
int min=max;
int px=0,py=0;
for(int i=0;i<=xr+1;i++) {
for(int j=0;j<=yr+1;j++) {
mp[i][j]=max;
}
}
for(int i=1;i<=xr;i++) {
read=br.readLine().split(" ");
for(int j=1;j<=yr;j++) {
mp[i][j]=Integer.parseInt(read[j-1]);
if(min>mp[i][j]) {
min=mp[i][j];
px=i;
py=j;
}
}
}
long out=min;
int[] go=new int[4];
mp[px][py]=max;
while(true) {
min=max;
go[0]=mp[px+1][py];
go[1]=mp[px-1][py];
go[2]=mp[px][py+1];
go[3]=mp[px][py-1];
int dir=-1;
for(int i=0;i<4;i++) {
if(min>go[i]) {
dir=i;
min=go[i];
}
}
if(dir==-1)break;
if(dir==0)px++;
if(dir==1)px--;
if(dir==2)py++;
if(dir==3)py--;
mp[px][py]=max;
out+=min;
}
System.out.println(out);
}
}
```
---
### d093 方格棋盤的最少轉彎數路線
解法:BFS
```Java=
import java.io.*;
import java.util.*;
public class d093 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean[][] mp=new boolean[505][505];
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
final int n=Integer.parseInt(in[0]);
final int m=Integer.parseInt(in[1]);
int ans=-1,x,y;
pos p;
for(int i=1;i<=n;i++) {
in=br.readLine().split("");
for(int j=1;j<=m;j++) {
if(in[j-1].equals("0"))mp[i][j]=true;
}
}
Queue<pos> q=new LinkedList<>();
q.offer(new pos(1,1));
mp[1][1]=false;
q.offer(new pos(-1,-1));
while(!q.isEmpty()) {
p=q.poll();
if(p.x==-1) {
if(q.isEmpty()) {
ans=-1;
break;
}
ans++;
q.offer(p);
continue;
}
if(p.x==n&&p.y==m)break;
x=p.x+1;
y=p.y;
while(mp[x][y]) {
mp[x][y]=false;
q.offer(new pos(x,y));
x++;
}
x=p.x-1;
y=p.y;
while(mp[x][y]) {
mp[x][y]=false;
q.offer(new pos(x,y));
x--;
}
x=p.x;
y=p.y+1;
while(mp[x][y]) {
mp[x][y]=false;
q.offer(new pos(x,y));
y++;
}
x=p.x;
y=p.y-1;
while(mp[x][y]) {
mp[x][y]=false;
q.offer(new pos(x,y));
y--;
}
}
if(ans!=-1)System.out.println(ans);
else {
System.out.println(-1);
}
}
}
class pos{
int x,y;
pos(int a,int b){
x=a;
y=b;
}
}
```
---
### d094 闖關路線
解法:BFS
```Java=
import java.io.*;
import java.util.*;
public class d094 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt=0;
public static boolean neg;
public static int[] mp=new int[1000005];
public static boolean[] vis=new boolean[1000005];
public static void main(String[] args) throws Exception{
final int n=orz();
final int p=orz();
final int l=orz();
final int r=orz();
int pl,m;
for(int i=0;i<n;i++)mp[i]=orz();
Queue<Integer> q=new LinkedList<>();
vis[0]=true;
q.offer(0);
q.offer(-1);
while(!q.isEmpty()) {
pl=q.poll();
if(pl==p)break;
if(pl==-1) {
if(q.isEmpty()) {
cnt=-1;
break;
}
cnt++;
q.offer(-1);
continue;
}
if(pl-l>=0) {
m=mp[pl-l];
if(m>=0&&m<n) {
if(!vis[m]){
q.offer(m);
vis[m]=true;
}
}
}
if(pl+r<n) {
m=mp[pl+r];
if(m>=0&&m<n) {
if(!vis[m]){
q.offer(m);
vis[m]=true;
}
}
}
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d095 DAG 的最長與最短路徑
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d095 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,s,b,c,d;
static boolean neg,e=false;
static ArrayList<ArrayList<pair>> a=new ArrayList<>();
static int[] min=new int[100005];
static int[] max=new int[100005];
static boolean[] vis=new boolean[100005];
public static void main(String[] args) throws Exception{
new Thread(null,new d095(),"",1<<26).start();
}
public void run() {
final int n=orz();
final int m=orz();
s=orz();
final int t=orz();
Arrays.fill(min,1<<30);
Arrays.fill(max,1<<30);
for(int i=0;i<n;i++)a.add(new ArrayList<pair>());
for(int i=0;i<m;i++) {
b=orz();
c=orz();
d=orz();
a.get(c).add(new pair(b,d));
}
dfs(t);
if(e) {
System.out.println(min[t]);
System.out.println(max[t]);
}
else {
System.out.println("No path");
System.out.println("No path");
}
}
static pair dfs(int x) {
if(x==s)return new pair(0,0);
if(vis[x]) {
e=true;
return new pair(min[x],max[x]);
}
vis[x]=true;
int mn=1<<30,mx=-(1<<30);
pair q;
for(pair i:a.get(x)) {
q=dfs(i.x);
mn=Math.min(q.x+i.y,mn);
mx=Math.max(q.y+i.y,mx);
}
min[x]=mn;
max[x]=mx;
return new pair(mn,mx);
}
static int orz(){
ret=0;
neg=false;
try {r=br.read();
} catch (Exception e) {}
if(r=='-') {
neg=true;
try {r=br.read();
} catch (Exception e) {}
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
if(neg)ret*=-1;
return ret;
}
}
class pair{
int x,y;
pair(int a,int b){
x=a;
y=b;
}
}
```
---
### d096 最短路徑
解法:Dijkstra's Algorithm
```Java=
import java.util.*;
import java.io.*;
public class d096 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,mx=0,cnt=0;
public static boolean[] vis=new boolean[100005];
public static ArrayList<ArrayList<P>> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
int x,y,z;
P pl;
PriorityQueue<P> pq=new PriorityQueue<>(new Comparator<P>() {
public int compare(P f,P s) {
return f.w-s.w;
}
});
for(int i=0;i<n;i++)a.add(new ArrayList<P>());
for(int i=0;i<m;i++) {
x=orz();
y=orz();
z=orz();
a.get(x).add(new P(y,z));
a.get(y).add(new P(x,z));
}
pq.offer(new P(0,0));
while(!pq.isEmpty()) {
pl=pq.poll();
if(vis[pl.n])continue;
vis[pl.n]=true;
mx=Math.max(mx,pl.w);
for(P i:a.get(pl.n)) {
pq.offer(new P(i.n,pl.w+i.w));
}
}
for(int i=0;i<n;i++)if(!vis[i])cnt++;
System.out.println(mx);
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class P{
int n,w;
P(int a,int b){
n=a;
w=b;
}
}
```
---
### d097 挖坑跳
解法:DSU
```Java=
import java.io.*;
import java.util.*;
public class d097 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt=0,max=0,ta=0,tn=0;
public static boolean[][] w=new boolean[505][505];
public static int[][] a=new int[505][505];
public static P[][] dsu=new P[505][505];
public static P top,aa;
public static void main(String[] args) throws Exception{
final int m=orz();
final int n=orz();
final int k=orz();
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dsu[i][j]=new P(i,j);
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(orz()==1) {
cnt++;
a[i][j]=1;
w[i][j]=true;
aa=new P(i,j);
if(w[i-1][j])union(aa,new P(i-1,j));
if(w[i+1][j])union(aa,new P(i+1,j));
if(w[i][j-1])union(aa,new P(i,j-1));
if(w[i][j+1])union(aa,new P(i,j+1));
}
}
}
tn+=cnt;
ta+=max;
int i=0,j=0;
for(int q=0;q<k;q++) {
i=orz();
j=orz();
if(!w[i][j]) {
cnt++;
a[i][j]=1;
w[i][j]=true;
aa=new P(i,j);
if(w[i-1][j])union(aa,new P(i-1,j));
if(w[i+1][j])union(aa,new P(i+1,j));
if(w[i][j-1])union(aa,new P(i,j-1));
if(w[i][j+1])union(aa,new P(i,j+1));
}
tn+=cnt;
ta+=max;
}
System.out.println(ta);
System.out.println(tn);
}
public static void union(P f,P s) {
query(f);
query(s);
P u=dsu[f.x][f.y];
P v=dsu[s.x][s.y];
if(u.x==v.x&&u.y==v.y) {
return;
}
cnt--;
if(u.x*1000+v.y>u.x*1000+v.y) {
dsu[u.x][u.y]=new P(v.x,v.y);
a[v.x][v.y]+=a[u.x][u.y];
max=Math.max(a[v.x][v.y],max);
}
else {
dsu[v.x][v.y]=new P(u.x,u.y);
a[u.x][u.y]+=a[v.x][v.y];
max=Math.max(a[u.x][u.y],max);
}
}
public static void query(P a) {
if(dsu[a.x][a.y].x==a.x&&dsu[a.x][a.y].y==a.y) {
top=new P(a.x,a.y);
return;
}
query(dsu[a.x][a.y]);
dsu[a.x][a.y]=new P(top.x,top.y);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class P{
int x,y;
P(int a,int b){
x=a;
y=b;
}
}
```
---
### d098 最小生成樹
解法:Kruskal's algorithm
```Java=
import java.io.*;
import java.util.*;
public class d098 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt=0,cost=0,top,idx=0;
public static int[] dsu=new int[100005];
public static ArrayList<P> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
for(int i=0;i<n;i++)dsu[i]=i;
for(int i=0;i<m;i++) {
a.add(new P(orz(),orz(),orz()));
}
Collections.sort(a,new Comparator<P>() {
public int compare(P f,P s) {
return f.w-s.w;
}
});
for(;idx<m;idx++) {
if(cnt==n-1)break;
union(a.get(idx).x,a.get(idx).y);
}
if(cnt==n-1) {
System.out.println(cost);
}
else {
System.out.println(-1);
}
}
public static void union(int f,int s) {
query(f);
query(s);
if(dsu[f]==dsu[s])return;
cnt++;
cost+=a.get(idx).w;
if(dsu[f]>dsu[s]) {
dsu[dsu[s]]=dsu[f];
}
else {
dsu[dsu[f]]=dsu[s];
}
}
public static void query(int x) {
if(dsu[x]==x) {
top=x;
return;
}
query(dsu[x]);
dsu[x]=top;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class P{
int x,y,w;
P(int a,int b,int c){
x=a;
y=b;
w=c;
}
}
```
---
### d099 AOV 最早完工時間
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d099 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
static int ret,r;
static ArrayList<ArrayList<Integer>> e=new ArrayList<>();
static ArrayList<ArrayList<Integer>> e2=new ArrayList<>();
static ArrayList<Integer> out=new ArrayList<>();
static int[] dp=new int[10005];
static int[] ct=new int[10005];
public static void main(String[] args) throws Exception{
new Thread(null,new d099(),"",1<<26).start();
}
public void run() {
final int n=orz();
final int m=orz();
int a,b,pre=-1;
for(int i=0;i<=n+1;i++)e.add(new ArrayList<Integer>());
for(int i=0;i<=n+1;i++)e2.add(new ArrayList<Integer>());
for(int i=1;i<=n;i++)ct[i]=orz();
for(int i=0;i<m;i++) {
a=orz();
b=orz();
e.get(b).add(a);
}
for(int i=1;i<=n;i++) {
e.get(n+1).add(i);
}
System.out.println(dfs(n+1));
for(int i:e2.get(n+1)) {
dfs2(i);
}
Collections.sort(out);
for(int i:out) {
if(pre==i)continue;
pre=i;
try {
bw.write(i+" ");
} catch (IOException e) {}
}
try {
bw.flush();
} catch (IOException e) {}
}
static int dfs(int x) {
if(dp[x]!=0)return dp[x];
int mx=ct[x],c;
for(int i:e.get(x)) {
c=dfs(i)+ct[x];
if(c==mx) {
e2.get(x).add(i);
}
else if(c>mx) {
mx=c;
e2.get(x).clear();
e2.get(x).add(i);
}
}
dp[x]=mx;
return dp[x];
}
static void dfs2(int x) {
out.add(x);
for(int i:e2.get(x)) {
dfs2(i);
}
}
static int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d100 小寶的著色問題
解法:二分圖判斷
```Java=
import java.io.*;
import java.util.*;
public class d100 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
static ArrayList<ArrayList<Integer>> e=new ArrayList<>();
static boolean solve;
static int ret,r;
static int[] vis=new int[10005];
public static void main(String[] args) throws Exception{
new Thread(null,new d100(),"",1<<26).start();
}
public void run() {
final int t=orz();
int n,m,a,b;
for(int i=0;i<t;i++) {
e.clear();
Arrays.fill(vis,-1);
n=orz();
m=orz();
solve=true;
for(int j=0;j<n;j++)e.add(new ArrayList<Integer>());
for(int j=0;j<m;j++) {
a=orz();
b=orz();
e.get(a).add(b);
e.get(b).add(a);
}
for(int j=0;j<n;j++) {
if(vis[j]==-1)dfs(j,1);
if(!solve)break;
}
if(solve)System.out.println("yes");
else {
System.out.println("no");
}
}
}
static void dfs(int x,int pre) {
if(vis[x]!=-1) {
if(vis[x]==pre)solve=false;
return;
}
vis[x]=pre^1;
for(int i:e.get(x)) {
dfs(i,vis[x]);
}
}
static int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
## d101~last
### d101 紅白彩帶
解法:DSU+二分搜
```Java=
import java.io.*;
import java.util.*;
public class d101 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,top,max=1,ta=0,tb=0,bis;
public static boolean[] f=new boolean[100005];
public static int[] l=new int[100005];
public static int[] dsu=new int[100005];
public static ArrayList<Integer> min=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=orz();
final int k=orz();
int in;
for(int i=1;i<=n;i++) {
dsu[i]=i;
f[i]=(orz()==1)?true:false;
if(f[i]) {
l[i]=1;
min.add(0,1);
if(f[i-1]) {
union(i-1,i);
}
}
}
ta+=max;
tb+=min.get(0);
for(int i=0;i<k;i++) {
in=orz();
f[in]=true;
l[in]=1;
min.add(0,1);
if(f[in+1])union(in,in+1);
if(f[in-1])union(in-1,in);
ta+=max;
tb+=min.get(0);
}
System.out.println(ta);
System.out.println(tb);
}
public static void union(int f,int s) {
query(f);
query(s);
bis=Collections.binarySearch(min,l[dsu[f]]);
min.remove(bis);
bis=Collections.binarySearch(min,l[dsu[s]]);
min.remove(bis);
l[dsu[f]]+=l[dsu[s]];
bis=Collections.binarySearch(min,l[dsu[f]]);
if(bis<0)bis=bis*-1-1;
min.add(bis,l[dsu[f]]);
dsu[dsu[s]]=dsu[f];
if(max<l[dsu[f]])max=l[dsu[f]];
}
public static void query(int x) {
if(dsu[x]==x) {
top=x;
return;
}
query(dsu[x]);
dsu[x]=top;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d102 樹上的推銷員
解法:DFS
```Java=
import java.util.*;
import java.io.*;
public class d102 implements Runnable{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,cnt=0,x,y;
public static ArrayList<Integer> out=new ArrayList<>();
public static ArrayList<ArrayList<Integer>> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
new Thread(null,new d102(),"",1<<26).start();
}
public void run() {
final int n=orz();
for(int i=0;i<n;i++)a.add(new ArrayList<Integer>());
for(int i=0;i<n-1;i++) {
x=orz();
y=orz();
a.get(x).add(y);
a.get(y).add(x);
cnt+=(orz()*2);
}
dfs(0,-1);
try {bw.write(cnt+"\n");} catch (IOException e) {}
for(int i:out) {
try {bw.write(i+" ");} catch (IOException e) {}
}
try {bw.flush();} catch (IOException e) {}
}
void dfs(int x,int pre) {
out.add(x);
Collections.sort(a.get(x));
for(int i:a.get(x)) {
if(i==pre)continue;
dfs(i,x);
out.add(x);
}
}
int orz(){
ret=0;
try {
r=br.read();
} catch (IOException e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {
r=br.read();
} catch (IOException e) {}
}
return ret;
}
}
```
---
### d103 物流派送系統
解法:DFS
```Java=
import java.util.*;
import java.io.*;
public class d103 implements Runnable{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,x,y,ma=0,mb=0;
public static ArrayList<ArrayList<pii>> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
new Thread(null,new d103(),"",1<<26).start();
}
public void run() {
final int n=orz();
for(int i=0;i<n;i++)a.add(new ArrayList<pii>());
for(int i=1;i<=n-1;i++) {
x=orz();
y=orz();
a.get(i).add(new pii(x,y));
a.get(x).add(new pii(i,y));
}
dfs(0,0,-1,0);
System.out.println(ma);
System.out.println(mb);
}
void dfs(int x,int leng,int pre,int cur) {
if(leng>ma)ma=leng;
if(cur>mb)mb=cur;
for(pii i:a.get(x)) {
if(i.x==pre)continue;
dfs(i.x,leng+i.y,x,cur+1);
}
}
int orz(){
ret=0;
try {
r=br.read();
} catch (IOException e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {
r=br.read();
} catch (IOException e) {}
}
return ret;
}
}
class pii{
int x,y;
pii(int a,int b){
x=a;
y=b;
}
}
```
---
### d104 購物中心選位置
解法:樹重心
```Java=
import java.io.*;
import java.util.*;
public class d104 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static fa[] a=new fa[100005];
public static int[] son=new int[100005];
public static int[] node=new int[100005];
public static int ret,r,cent=-1;
public static void main(String[] args) throws Exception{
final int n=orz();
final double d=n/2;
int x,y;
long cnt=0;
fa p;
a[0]=new fa(0,0,0);
for(int i=1;i<=n-1;i++) {
x=orz();
y=orz();
a[i]=new fa(i,x,y);
son[x]++;
}
Queue<fa> q=new LinkedList<>();
for(int i=0;i<n;i++) {
if(son[i]==0) {
q.offer(a[i]);
}
}
Arrays.fill(node,1);
while(!q.isEmpty()) {
p=q.poll();
if(cent==-1&&node[p.a]>=d) {
cent=p.a;
}
if(p.a==0)continue;
node[p.b]+=node[p.a];
cnt+=Math.min(node[p.a],n-node[p.a])*p.c;
son[p.b]--;
if(son[p.b]==0)q.offer(a[p.b]);
}
System.out.println(cent);
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class fa{
int a,b,c;
fa(int x,int y,int z){
a=x;
b=y;
c=z;
}
}
```
---
### d105 自動分裝
解法:DFS
```Java=
import java.io.*;
public class d105 implements Runnable{
public static int ret,r,n,m,w;
public static int[] ow,nw;
public static int[][] node,cw;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
new Thread(null,new d105(),"",1<<26).start();
}
public void run() {
n=readnum();
m=readnum();
ow=new int[n];
nw=new int[m];
node=new int[n][2];
cw=new int[n][2];
for(int i=0;i<n;i++)ow[i]=readnum();
for(int i=0;i<m;i++)nw[i]=readnum();
int f;
for(int i=0;i<n-1;i++) {
f=readnum();
node[f][0]=readnum();
node[f][1]=readnum();
}
setup(1);
for(int i=0;i<m;i++) {
w=nw[i];
put(1);
}
try {
bw.flush();
} catch (IOException e) {
}
System.exit(0);
}
static int readnum() {
ret=0;
try {
r=br.read();
} catch (IOException e) {
}
while(r>47&&r<58) {
ret*=10;
r-=48;
ret+=r;
try {r=br.read();} catch (IOException e) {}
}
return ret;
}
static int setup(int x) {
if(x>=n) {
return ow[x-n];
}
cw[x][0]=setup(node[x][0]);
cw[x][1]=setup(node[x][1]);
return cw[x][0]+cw[x][1];
}
static void put(int x) {
if(x>=n) {
try {bw.write(x+" ");} catch (IOException e) {}
return;
}
if(cw[x][0]<=cw[x][1]) {
cw[x][0]+=w;
put(node[x][0]);
}
else {
cw[x][1]+=w;
put(node[x][1]);
}
}
}
```
---
### d106 寶石的顏色
解法:DFS、undo、離散化
```Java=
import java.io.*;
import java.util.*;
public class d106 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
static HashMap<Integer,Integer> mp=new HashMap<>();
static int ret,r,max=0,cnt=0;
static int[] d=new int[1000005];
static int[] num=new int[1000005];
static ArrayList<ArrayList<Integer>> e=new ArrayList<>();
public static void main(String[] args) throws Exception{
new Thread(null,new d106(),"",1<<26).start();
}
public void run() {
final int n=orz();
int a,b;
for(int i=0;i<n;i++)e.add(new ArrayList<Integer>());
for(int i=0;i<n;i++) {
d[i]=orz();
if(mp.get(d[i])==null)mp.put(d[i],cnt++);
}
for(int i=0;i<n-1;i++) {
a=orz();
b=orz();
e.get(a).add(b);
e.get(b).add(a);
}
dfs(0,-1);
System.out.println(max);
System.exit(0);
}
void dfs(int x,int pre) {
int g=mp.get(d[x]);
num[g]++;
if(num[g]>max)max=num[g];
for(int i:e.get(x)) {
if(i==pre)continue;
dfs(i,x);
}
num[g]--;
}
int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d107 樹的最大獨立集
解法:Greedy
```Java=
import java.io.*;
import java.util.*;
public class d107 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret,cnt=0;
public static int[] fa=new int[100005];
public static int[] so=new int[100005];
public static boolean[] t=new boolean[100005];
public static void main(String[] args) throws Exception{
final int n=orz();
int a,p;
for(int i=1;i<n;i++) {
a=orz();
fa[i]=a;
so[a]++;
}
Queue<Integer> q=new LinkedList<>();
Arrays.fill(t,true);
for(int i=0;i<n;i++) {
if(so[i]==0)q.offer(i);
}
while(!q.isEmpty()) {
p=q.poll();
if(t[p]) {
cnt++;
t[fa[p]]=false;
}
so[fa[p]]--;
if(so[fa[p]]==0) {
q.offer(fa[p]);
}
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class fa{
int a,b,c;
fa(int x,int y,int z){
a=x;
b=y;
c=z;
}
}
```
---
### d108 樹狀圖的距離總和
解法:遞迴
```Java=
import java.io.*;
import java.util.*;
public class d108 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static fa[] a=new fa[100005];
public static int[] son=new int[100005];
public static int[] node=new int[100005];
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int x;
long cnt=0;
fa p;
a[1]=new fa(1,1,0);
for(int i=2;i<=n;i++) {
x=orz();
a[i]=new fa(i,x,0);
son[x]++;
}
for(int i=2;i<=n;i++) {
a[i].c=orz();
}
Queue<fa> q=new LinkedList<>();
for(int i=1;i<=n;i++) {
if(son[i]==0) {
q.offer(a[i]);
}
}
Arrays.fill(node,1);
while(!q.isEmpty()) {
p=q.poll();
if(p.a==1)continue;
node[p.b]+=node[p.a];
cnt+=(((long)node[p.a]*(n-node[p.a]))*p.c)*2;
son[p.b]--;
if(son[p.b]==0)q.offer(a[p.b]);
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class fa{
int a,b,c;
fa(int x,int y,int z){
a=x;
b=y;
c=z;
}
}
```
---
### d109 公司派對
解法:DP tree
```Java=
import java.io.*;
import java.util.*;
public class d109 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt;
static ArrayList<ArrayList<Integer>> s=new ArrayList<>();
static int[] p=new int[100005];
static int[] dp0=new int[100005];
static int[] dp1=new int[100005];
public static void main(String[] args) throws Exception{
new Thread(null,new d109(),"",1<<26).start();
}
public void run() {
final int n=orz();
int in;
p[1]=orz();
for(int i=0;i<=n;i++)s.add(new ArrayList<Integer>());
for(int i=2;i<=n;i++) {
in=orz();
s.get(in).add(i);
p[i]=orz();
}
dfs(1);
System.out.println(Math.max(dp0[1],dp1[1]));
}
void dfs(int x) {
for(int i:s.get(x)) {
dfs(i);
}
cnt=0;
for(int i:s.get(x)) {
cnt+=dp0[i];
}
dp1[x]=cnt+p[x];
cnt=0;
for(int i:s.get(x)) {
cnt+=Math.max(dp0[i],dp1[i]);
}
dp0[x]=cnt;
}
int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d110 不同成本的購物中心
解法:DP tree
```Java=
import java.io.*;
import java.util.*;
public class d110 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt;
static ArrayList<ArrayList<Integer>> s=new ArrayList<>();
static int[] p=new int[100005];
static int[] dp0=new int[100005];
static int[] dp1=new int[100005];
static int[] dp2=new int[100005];
public static final int inf=1<<30;
public static void main(String[] args) throws Exception{
new Thread(null,new d110(),"",1<<26).start();
}
public void run() {
int a,b;
final int n=orz();
for(int i=0;i<=n;i++)s.add(new ArrayList<Integer>());
for(int i=1;i<=n;i++)p[i]=orz();
for(int i=0;i<n-1;i++) {
a=orz();
b=orz();
s.get(a).add(b);
s.get(b).add(a);
}
dfs(1,-1);
System.out.println(Math.min(dp1[1],dp2[1]));
}
void dfs(int x,int pre) {
boolean leaf=true,select;
int min=1<<30;
for(int i:s.get(x)) {
if(i==pre)continue;
dfs(i,x);
leaf=false;
}
if(leaf) {
dp0[x]=0;
dp1[x]=inf;
dp2[x]=p[x];
return;
}
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp1[i],dp2[i]);
}
dp0[x]=cnt;
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp2[i],dp1[i]);
min=Math.min(dp2[i]-dp1[i],min);
}
dp1[x]=cnt+Math.max(0,min);
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp0[i],Math.min(dp1[i],dp2[i]));
}
dp2[x]=cnt+p[x];
}
int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d111 血緣關係
解法:BFS
```Java=
import java.io.*;
import java.util.*;
public class d111 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static ArrayList<ArrayList<Integer>> a=new ArrayList<>();
public static int ret,r,ans=-1;
public static long root;
public static boolean[] vis=new boolean[100005];
public static void main(String[] args) throws Exception{
final int n=orz();
int x,y,p=-1;
for(int i=0;i<n;i++)a.add(new ArrayList<Integer>());
root=(n-1)*n/2;
for(int i=0;i<n-1;i++) {
x=orz();
y=orz();
a.get(x).add(y);
a.get(y).add(x);
root-=y;
}
Queue<Integer> q=new LinkedList<>();
q.offer((int)root);
while(!q.isEmpty()) {
p=q.poll();
vis[p]=true;
for(int i:a.get(p)) {
if(!vis[i])q.offer(i);
}
}
q.offer(p);
q.offer(-1);
Arrays.fill(vis,false);
while(!q.isEmpty()) {
p=q.poll();
if(p==-1) {
ans++;
if(!q.isEmpty())q.offer(-1);
continue;
}
vis[p]=true;
for(int i:a.get(p)) {
if(!vis[i])q.offer(i);
}
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d112 服務中心選位置
解法:DP
```Java=
mport java.io.*;
import java.util.*;
public class d112 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt;
static ArrayList<ArrayList<Integer>> s=new ArrayList<>();
static int[] dp0=new int[100005];
static int[] dp1=new int[100005];
static int[] dp2=new int[100005];
public static final int inf=1<<30;
public static void main(String[] args) throws Exception{
new Thread(null,new d112(),"",1<<26).start();
}
public void run() {
int a,b;
final int n=orz();
for(int i=0;i<=n;i++)s.add(new ArrayList<Integer>());
for(int i=0;i<n-1;i++) {
a=orz();
b=orz();
s.get(a).add(b);
s.get(b).add(a);
}
dfs(1,-1);
System.out.println(Math.min(dp1[1],dp2[1]));
}
void dfs(int x,int pre) {
boolean leaf=true;
int min=1<<30;
for(int i:s.get(x)) {
if(i==pre)continue;
dfs(i,x);
leaf=false;
}
if(leaf) {
dp0[x]=0;
dp1[x]=inf;
dp2[x]=1;
return;
}
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp1[i],dp2[i]);
}
dp0[x]=cnt;
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp2[i],dp1[i]);
min=Math.min(dp2[i]-dp1[i],min);
}
dp1[x]=cnt+Math.max(0,min);
cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
cnt+=Math.min(dp0[i],Math.min(dp1[i],dp2[i]));
}
dp2[x]=cnt+1;
}
int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d113 竊聽間諜網
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d113 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,cnt;
static ArrayList<ArrayList<Integer>> s=new ArrayList<>();
static int[] dp0=new int[100005];
static int[] dp1=new int[100005];
public static final int inf=1<<30;
public static void main(String[] args) throws Exception{
new Thread(null,new d113(),"",1<<26).start();
}
public void run() {
final int n=orz();
for(int i=0;i<n;i++)s.add(new ArrayList<Integer>());
for(int i=1;i<n;i++) {
s.get(orz()).add(i);
}
dfs(0);
System.out.println(Math.min(dp0[0],dp1[0]));
}
void dfs(int x) {
int min=1<<30;
for(int i:s.get(x))dfs(i);
cnt=0;
for(int i:s.get(x)) {
cnt+=Math.min(dp0[i],dp1[i]);
}
dp1[x]=cnt+1;
cnt=0;
for(int i:s.get(x)) {
cnt+=dp1[i];
}
dp0[x]=cnt;
}
int orz() {
ret=0;
try {r=br.read();
} catch (Exception e) {}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
try {r=br.read();
} catch (Exception e) {}
}
return ret;
}
}
```
---
### d114 佔領連續的城鎮
解法:DP
```Java=
import java.io.*;
import java.util.*;
public class d114 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,ans=0;
static ArrayList<ArrayList<Integer>> s=new ArrayList<>();
static int[] dp=new int[100005];
static int[] mp=new int[100005];
static boolean neg;
public static void main(String[] args) throws Exception{
new Thread(null,new d114(),"",1<<26).start();
}
public void run() {
final int n=orz();
int a,b;
for(int i=0;i<=n;i++)s.add(new ArrayList<Integer>());
for(int i=1;i<=n;i++)mp[i]=orz();
for(int i=1;i<n;i++) {
a=orz();
b=orz();
s.get(a).add(b);
s.get(b).add(a);
}
dfs(1,-1);
System.out.println(ans);
}
void dfs(int x,int pre) {
int cnt=0;
for(int i:s.get(x)) {
if(i==pre)continue;
dfs(i,x);
cnt+=Math.max(0,dp[i]);
}
dp[x]=cnt+mp[x];
ans=Math.max(dp[x],ans);
}
int orz() {
ret=0;
neg=false;
re();
if(r=='-') {
neg=true;
re();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
re();
}
if(neg)ret*=-1;
return ret;
}
void re() {
try {r=br.read();
} catch (Exception e) {}
}
}
```
---
### d115 樹上一位不回家的推銷員
解法:DFS
```Java=
import java.io.*;
import java.util.*;
public class d115 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int ret,r,ans=0;
static ArrayList<ArrayList<edge>> s=new ArrayList<>();
static int[] d=new int[50005];
static boolean neg;
public static void main(String[] args) throws Exception{
new Thread(null,new d115(),"",1<<26).start();
}
public void run() {
final int n=orz();
for(int i=0;i<n;i++)s.add(new ArrayList<edge>());
int a,b,c,mx=0,idx=-1;
for(int i=0;i<n-1;i++) {
a=orz();
b=orz();
c=orz();
ans+=(c*2);
s.get(a).add(new edge(b,c));
s.get(b).add(new edge(a,c));
}
dfs(0,0,-1);
for(int i=0;i<n;i++) {
if(d[i]>mx) {
mx=d[i];
idx=i;
}
}
dfs(idx,0,-1);
for(int i=0;i<n;i++) {
if(d[i]>mx) {
mx=d[i];
}
}
System.out.println(ans-mx);
}
void dfs(int x,int l,int pre) {
d[x]=l;
for(edge i:s.get(x)) {
if(i.n==pre)continue;
dfs(i.n,l+i.l,x);
}
}
int orz() {
ret=0;
neg=false;
re();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
re();
}
return ret;
}
void re() {
try {r=br.read();
} catch (Exception e) {}
}
}
class edge{
int n,l;
edge(int a,int b){
n=a;
l=b;
}
}
```
---
### d116 病毒演化
解法:DP tree
```Java=
import java.io.*;
import java.util.*;
public class d116 {
public static ArrayList<ArrayList<Integer>> son=new ArrayList<>();
public static String[] base;
public static int[][] dp;
public static HashMap<Character,Integer> mp=new HashMap<>();
public static final int max=1<<30;
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] in=br.readLine().split(" ");
int n=Integer.parseInt(in[0]);
int l=Integer.parseInt(in[1]);
setup(n);
int fa,sn,root=-1;
for(int i=0;i<n;i++) {
in=br.readLine().split(" ");//read
sn=Integer.parseInt(in[0]);
fa=Integer.parseInt(in[1]);
base[sn]=in[2];
if(fa==sn) {
root=fa;//root
continue;
}
son.get(fa).add(sn);//加節點
}
int variety=0;
int min;
for(int i=0;i<l;i++) {
for(int k=0;k<4;k++) {
dp[root][k]=max;
}
//initialize
dfs(root,i);
//dfs
min=max;
//find DP min
for(int j=0;j<4;j++) {
if(min>dp[root][j]) {
min=dp[root][j];
}
}
variety+=min;
}
System.out.println(variety);
}
public static void dfs(int n,int x) {
int id=mp.get(base[n].charAt(x));//父節點鹼基
if(son.get(n).isEmpty()) {
//樹節點
if(id==4) { //@
for(int i=0;i<4;i++) {
dp[n][i]=0;
}
}
else { //A U C G
dp[n][id]=0;
}
return;
}
//other node
for(int i:son.get(n)) {
dfs(i,x);
}
int id2,l,r;
l=(id==4)?0:id;
r=(id==4)?4:id+1;
for(int j=l;j<r;j++) {
dp[n][j]=0;
for(int i:son.get(n)) {
id2=mp.get(base[i].charAt(x));//子孫鹼基
if(id2==4){//son=@
dp[n][j]+=alpha(n,j,i);
}
else if(id2==j) {//same
dp[n][j]+=dp[i][id2];
}
else {//not the same
dp[n][j]+=dp[i][id2]+1;
}
}
}
}
public static void setup(int n) {
//變數定義
dp=new int[n+1][4];//dp
base=new String[n+1];//鹼基
mp.put('A',0);//A->0
mp.put('U',1);
mp.put('C',2);
mp.put('G',3);
mp.put('@',4);
for(int i=0;i<=n;i++)son.add(new ArrayList<Integer>());
}
public static int alpha(int n,int idn,int m) {
int mn=max;//找尋變異最小的子節點;
for(int i=0;i<4;i++) {
if(idn==i) {
if(mn>dp[m][i]) {
mn=dp[m][i];
}
}
else {
if(mn>dp[m][i]+1) {
mn=dp[m][i]+1;
}
}
}
return mn;
}
}
```
---
### d118 山寨華山論劍
解法:sort、DP
```Java=
import java.io.*;
import java.util.*;
public class d118 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,max;
public static void main(String[] args) throws Exception{
final int n=orz();
oq p;
ac[] a=new ac[n];
for(int i=0;i<n;i++) {
a[i]=new ac(orz(),orz(),orz());
}
Arrays.sort(a,new Comparator<ac>() {
public int compare(ac f,ac s) {
return f.l-s.l;
}
});
PriorityQueue<oq> pq=new PriorityQueue<>(new Comparator<oq>() {
public int compare(oq f,oq s) {
return f.r-s.r;
}
});
for(int i=0;i<n;i++) {
while(!pq.isEmpty()) {
p=pq.poll();
if(p.r>=a[i].l) {
pq.offer(p);
break;
}
max=Math.max(p.val,max);
}
pq.offer(new oq(a[i].r,max+a[i].val));
}
while(!pq.isEmpty()) {
p=pq.poll();
max=Math.max(p.val,max);
}
System.out.println(max);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class ac{
int l,r,val;
ac(int x,int y,int z){
l=x;
r=y;
val=z;
}
}
class oq{
int r,val;
oq(int x,int y){
r=x;
val=y;
}
}
```
---
Sign in with Wallet
Connect another wallet