TOI 2021.11 潛力組(二) 校隊(School Team) Java 解題心得( 題目 )
解題概念:DP
更新:這題可以greedy，詳見下方!
解題方法:我們令dp[i][j]=在前i+j個班選i個男、j個女的最小時間sum，其實我們就可以得到最小值dp[n][m]。
轉移式:dp[i][j]=min(dp[i-1][j]+boy[i+j], dp[i][j-1]+girl[i+j])
(註:這裡設班級從1開始，boy[i]代表第i班男生時間，girl[i]代表第i班女生時間)
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
public class zjg774 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret;
public static int[][] dp=new int[2005][2005];
public static int[][] in=new int[2][4005];//輸入
public static void main(String[] args) throws Exception {
int n=readint();
int m=readint();
for(int i=1;i<=n+m;i++) {
in[0][i]=readint();//男
in[1][i]=readint();//女
}
for(int i=1;i<=n;i++) {
dp[i][0]=dp[i-1][0]+in[0][i];
}
for(int j=1;j<=m;j++) {
dp[0][j]=dp[0][j-1]+in[1][j];//初始邊界
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
dp[i][j]=Math.min(dp[i-1][j]+in[0][i+j], dp[i][j-1]+in[1][i+j]);
}
}
System.out.println(dp[n][m]);
}
public static int readint() throws Exception {
//輸入
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
感謝fire5386 (fffelix)提供greedy解法:
用greedy 計算每個班級的差(男-女)然後排序 最大的n個取男生 剩下取女生
這樣似乎greedy的解法比較簡潔，而且複雜度也還不錯(甚至可以說比低批好)，下方提供比較一下:
DP O(mn)
Greedy O(tlogt) (假設總人數t=m+n)
文章標籤
全站熱搜
