TOI 2021.11 潛力組(一) 實境節目選角 Java 解題心得( 題目 )
說明:因為我的慣用語言不是C++，所以當時只有參加新手組，而潛力組的部分則是等ZJ上有題目才用Java補做。
解題概念:暴力窮舉
解題方法:雖然我們知道暴力法在數字大的時候不適用，可是在這題似乎是最簡單且可行的方法(n只有到17)。
我們會對每一個決策(是否要讓那個人參加比賽)進行遞迴，然後把他的朋友出現次數+1(當遞迴回到上一層的時候要undone之前所做結果)，然後如果遞回到某一層，現在拿的那個人他以前出現次數不為0則代表矛盾，也就是那裡不需繼續遞迴下去。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
public class zjg773 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret,n,best=0;
public static int[] cf=new int[20];//目前朋友出現次數
public static boolean[][] f=new boolean[20][20];
public static void main(String[] args) throws Exception {
n=readint();
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
f[i][j]=(readint()==1);
}
}
cur(1,1,true);
cur(1,0,false);
System.out.println(best);
}
public static void cur(int x,int s,boolean b) {
//x:目前算到第幾個
//s:目前取幾個
//b:目前這個要不要取
if(x>n) {
//比較結果
best=Math.max(best,s);
return;
}
if(b) {
for(int i=1;i<=n;i++) {
if(f[x][i]) {
cf[i]++;
}
}
if(cf[x]==0) {
if(x!=n)cur(x+1,s+1,true);
cur(x+1,s,false);//遞迴下一層
}
for(int i=1;i<=n;i++) {
//undo
if(f[x][i]) {
cf[i]--;
}
}
}
else {
if(x!=n)cur(x+1,s+1,true);
cur(x+1,s,false);
}
}
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;
}
}
文章標籤
全站熱搜
