第一行一个整数 表示放假天数
第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业
第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业
(1为营业 0为不营业)
一个整数,表示小Q休息的最少天数
4 1 1 0 0 0 1 1 0
2
小Q可以在第一天工作,第二天或第三天健身,小Q最少休息2天
import java.util.Scanner; /** * @Author: lei * @Date: 2020.3.18 10:21 */ public class Holiday { public static void main(String[] args) { //第一步数据处理:三行,就是三个字符串,后两行进行一个分割处理,然后再调用函数转换成为整型数据 Scanner in = new Scanner(System.in); String day_str = in.nextLine(); String [] work_str = in.nextLine().split(" "); String [] gym_str = in.nextLine().split(" "); int day = Integer.parseInt(day_str); //日期 int [] works = new int[day+1]; int [] gyms = new int[day+1]; for(int i = 1;i < day+1;i++) { works[i] = Integer.parseInt(work_str[i - 1]); gyms[i] = Integer.parseInt(gym_str[i-1]); } int res = holiday(day, works, gyms); System.out.println(res); } //策略:使用dp[i][0] dp[i][1] dp[i][2]分别记录在第i天如果是休息、工作、健身情况下,前i天有事做(也就是没休息)的最大天数 //如果第i天休息,那么前i天有事做的最大天数,实际就是dp[i-1][0] dp[i-1][1] dp[i-1][2]中的最大值 //如果第i天工作,那么前i天有事做的最大天数,就是前一天休息、健身中的最大值 + 1(因为第i天工作了,没有休息) //如果第i天健身,那么前i天有事做的最大天数,就是前一天休息、工作中的最大值 + 1(因为第i天健身了,没有休息) //最后的结果,就用day减去最大的做事天数,就是最少的休息时间了 public static int holiday(int day, int [] works, int [] gyms){ int res; int [][] dp = new int[day+1][3]; dp[0][0] = dp[0][1] = dp[0][2] = 0; for (int i = 1; i < day+1; i++) { if(works[i] == 1){ //第i天可以选择工作 dp[i][1] = Math.max(dp[i-1][0], dp[i-1][2]) + 1; } if(gyms[i] == 1){ //第i天可以选择健身 dp[i][2] = Math.max(dp[i-1][0], dp[i-1][1]) + 1; } dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2])); } res = day - Math.max(dp[day][0], Math.max(dp[day][1], dp[day][2])); return res; } }//class end
#include<bits/stdc++.h> using namespace std; using LL = int64_t; const int maxn=1e5+5; int dp[maxn][3],a[maxn],b[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) { dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]); dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][1]); } cout<<n-max(dp[n][0],dp[n][1]); return 0; }
最直观的想法,算是一种贪心吧。
n = int(input())//3 work = list(map(int,input().split())) gem = list(map(int,input().split())) workok,gemok,cnt = 0,0,0//标记当天能去哪里,0表示可以去,1表示不能去,cnt为放假天数 for i in range(n): if work[i] == 0 and gem[i] == 0://都不开放,必须休息 cnt += 1 workok,gemok = 0,0 continue if work[i] == 1 and gem[i] == 1://都开放,不能休息 if workok == 0 and gemok == 0://两者都能去,需要根据明天情况判断今天是去哪里 continue workok,gemok = gemok,workok//此时只允许去一个,状态对调 continue if work[i] == 1://只有公司开 if workok == 0: workok = 1 gemok = 0 continue cnt+=1 workok,gemok = 0,0 if gem[i] == 1://只有gem开 if gemok == 0: gemok = 1 workok = 0 continue cnt+=1 workok,gemok = 0,0 print(cnt)
#include<bits/stdc++.h> using namespace std; const int N = 100005; int a[N],b[N]; int n; int main(){ cin>>n; for(int i =1;i<=n;i++){ cin>>a[i]; } for(int i =1;i<=n;i++){ cin>>b[i]; } int res = 0; int flag = 0;//0都可以选,1只能a,2只能选b; for(int i =1;i<=n;i++){ if(a[i]==1&&b[i]==1&&flag==0){ continue; } if(a[i]==1&&b[i]==1&&flag==1){ flag =2; continue; } if(a[i]==1&&b[i]==1&&flag==2){ flag =1; continue; } if(a[i]==0&&b[i]==1&&(flag==2||flag==0)){ flag =1; continue; } if(a[i]==1&&b[i]==0&&(flag==1||flag==0)){ flag =2; continue; } res++; flag = 0; } cout<<res<<endl; return 0; }
n = int(input()) a = [int(value) for value in input().split()] b = [int(value) for value in input().split()] result = 0 previous_a = 0 previous_b = 0 for i in range(n): if a[i] == 0 and b[i] == 0: result += 1 previous_a = previous_b = 0 continue if a[i] == 1 and b[i] == 0: if previous_a == 1: result += 1 previous_a = previous_b = 0 continue else: previous_a = 1 previous_b = 0 continue if a[i] == 0 and b[i] == 1: if previous_b == 1: result += 1 previous_a = previous_b = 0 continue else: previous_a = 0 previous_b = 1 continue if a[i] == 1 and b[i] == 1: if previous_a == 1: previous_a = 0 previous_b = 1 continue if previous_b == 1: previous_b = 0 previous_a = 1 continue if previous_b == 0 and previous_a == 0: continue print(result)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] strIsWorking = br.readLine().trim().split(" "); String[] strIsGym = br.readLine().trim().split(" "); int[] isWorking = new int[n]; int[] isGym = new int[n]; for(int i = 0; i < n; i++){ isWorking[i] = Integer.parseInt(strIsWorking[i]); isGym[i] = Integer.parseInt(strIsGym[i]); } // dp[i][0],dp[i][1],dp[i][2]分别表示第i天 休息/锻炼/工作 累计的最小休息天数 int[][] dp = new int[n + 1][3]; for(int i = 1; i <= n; i++) for(int j = 0; j < 3; j++) dp[i][j] = Integer.MAX_VALUE; for(int i = 1; i <= n; i++){ // 今天健身房开门,锻炼从另外两种状态转移过来 if(isGym[i - 1] == 1) dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]); // 今天单位开门,工作从另外两种状态转移过来 if(isWorking[i - 1] == 1) dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]); // 休息可以从自身或另外两种状态转移而来 dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1; } System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]))); } }
let nDayoff = readline(); let workStr = readline(); let gymStr = readline(); let work = workStr.split(' ').map(Number); let gym = gymStr.split(' ').map(Number); let len = work.length; let dp = new Array(nDayoff + 1); for (let i = 0; i < nDayoff + 1; i++) { dp[i] = new Array(3).fill(Infinity); } //console.log("dp:", dp); dp[0][0] = dp[0][1] = dp[0][2] = 0; for (let i = 1; i <= len; i++) { if (gym[i - 1] === 1) { // 可以锻炼 dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]); } if (work[i - 1] === 1) { //可以工作 dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]); } //可以休息 dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1; } let res = Math.min(dp[len][0], Math.min(dp[len][1], dp[len][2])); console.log(res);
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] wo = new int[n]; for (int i = 0; i < n; i++) { wo[i] = in.nextInt(); } int[] ex = new int[n]; for (int i = 0; i < n; i++) { ex[i] = in.nextInt(); } System.out.println(minDay(wo, ex)); } } public static int minDay(int[] wo, int[] ex) { int n = wo.length; int[][] dp = new int[n][3]; // 0 休息,1 健身,2 工作 dp[0][0] = wo[0] == 0 && ex[0] == 0 ? 1 : 0; dp[0][1] = wo[0] == 0 ? Integer.MAX_VALUE : 0; dp[0][2] = ex[0] == 0 ? Integer.MAX_VALUE : 0; for (int i = 1; i < n; i++) { dp[i][2] = wo[i] == 1 ? Math.min(dp[i - 1][0], dp[i - 1][1]) : Integer.MAX_VALUE; dp[i][1] = ex[i] == 1 ? Math.min(dp[i - 1][0], dp[i - 1][2]) : Integer.MAX_VALUE; dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1; } return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])); } }
day=int(input()) _C=input() c=[int(i) for i in _C.split()] _G=input() g=[int(i) for i in _G.split()] a=[c.copy(),g.copy()] for i in range(day-1): if c[i]==0: a[0][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i] else: a[0][i+1]+=a[1][i] if g[i]==0: a[1][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i] else: a[1][i+1]+=a[0][i] print(day-(a[0][day-1] if a[0][day-1]>a[1][day-1] else a[1][day-1]))a[:][i]表示到第i天为止已经工作或运动的天数。
# include <iostream> # include <cstdlib> # include <cstring> # include <stack> # define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int main(void){ int n ; while(cin>>n){ int gym[n],i, work[n]; for ( i=0; i<n; ++i ) cin>>work[i]; for( i=0; i<n; ++i ) cin>>gym[i]; int dp[n+1][3]; // 0是休息,1是锻炼,2是工作 memset(dp, 0x3f, sizeof(dp)); dp[0][0] = dp[0][1] = dp[0][2] = 0; for ( int i=1; i<=n; ++i ){ if ( gym[i-1] == 1 ){ // 可以锻炼 dp[i][1] = min( dp[i-1][0], dp[i-1][2] ); } if ( work[i-1] == 1 ){ // 可以工作 dp[i][2] = min( dp[i-1][0], dp[i-1][1] ); } dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]))+1; } int res = min(dp[n][0], min(dp[n][1], dp[n][2])); cout<<res<<endl; } return 0; }
//1. 选择休息,故天数多1 dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) + 1; //2. 不休息,选择工作 dp[i][1] = min(dp[i-1][0], dp[i-1][2]); //3. 不休息,选择锻炼 dp[i][2] = min(dp[i-1][0], dp[i-1][1]); //边界:第0天休息天数为0 dp[0][i] = 0 (i = 1, 2, 3)
# include<iostream> # include<memory> using namespace std; int dp[100010][3]; int work[100010]; int train[100010]; int main(){ int n; cin >> n; for (int i = 0; i < n; i++){ cin >> work[i]; } for (int i = 0; i < n; i++){ cin >> train[i]; } memset(dp, 0x3f, sizeof(dp)); dp[0][0] = dp[0][1] = dp[0][2] = 0; for (int i = 1; i <= n; i++) { //看看今天是否能工作 if (work[i-1] == 1){ dp[i][1] = min(dp[i-1][0], dp[i-1][2]); } //看看今天是否能锻炼 if (train[i-1] == 1){ dp[i][2] = min(dp[i-1][0], dp[i-1][1]); } dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) + 1; //休息多1天 } int ans = min(dp[n][0], min(dp[n][1], dp[n][2])); cout << ans << endl; return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin >> n; vector<int> work(n), slp(n); for (int i = 0; i < n; ++i) cin >> work[i]; for (int i = 0; i < n; ++i) cin >> slp[i]; vector<vector<int>> dp(3, vector<int>(n + 1)); dp[0][0] = dp[1][0] = dp[2][0] = 0; for (int i = 1; i <= n; ++i) { dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[2][i - 1])); if (slp[i - 1]) { dp[1][i] = max(dp[2][i - 1], dp[0][i - 1]) + 1; } if (work[i - 1]) { dp[2][i] = max(dp[1][i - 1], dp[0][i - 1]) + 1; } } cout << n - max(dp[0][n], max(dp[1][n], dp[2][n])) << endl; return 0; }
#include <iostream> #include <vector> using namespace std; void printLeastRelax(vector<int> &a, vector<int> &b){ int n = a.size(); int dp0 = 1; int dp1 = a[0] ? 0 : n; int dp2 = b[0] ? 0 : n; for(int i = 1; i < n; ++i){ int prev_dp0 = dp0; int prev_dp1 = dp1; int prev_dp2 = dp2; dp0 = min(prev_dp0, min(prev_dp1, prev_dp2)) + 1; dp1 = a[i] ? min(prev_dp0, prev_dp2) : n; dp2 = b[i] ? min(prev_dp0, prev_dp1) : n; } cout << min(dp0, min(dp1, dp2)) << endl; } int main() { int n; vector<int> a; vector<int> b; cin >> n; a.resize(n); b.resize(n); for(int i = 0; i < n; ++i){ cin >> a[i]; } for(int i = 0; i < n; ++i){ cin >> b[i]; } printLeastRelax(a,b); } // 64 位输出请用 printf("%lld")
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt(); int[] nums1 = new int[n]; // 工作 int[] nums2 = new int[n]; // 健身 for (int i = 0; i < n; i++) { nums1[i] = in.nextInt(); } for (int i = 0; i < n; i++) { nums2[i] = in.nextInt(); } int work = 0; for (int i = 0; i < n; i++) { if (nums1[i] == 1 && nums2[i] == 1) { // 都为营业,选一个(不必关心具体选哪个) work++; } else if (nums1[i] == 1) { // 只营业一个,则就选营业的那个(贪心思想) work++; if (i + 1 < n) nums1[i + 1] = 0; // 选了营业的,就将对应的明天的营业状态置为0(因为不能两天选一家) } else if (nums2[i] == 1) { work++; if (i + 1 < n) nums2[i + 1] = 0; } } System.out.println(n - work); } } }
package tencent; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class Main { private static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] c = new int[n]; int[] y = new int[n]; for (int i = 0; i < n; i++) { c[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { y[i] = scanner.nextInt(); } backtrack(-1, c, y, 0, n, 0); System.out.println(min); } /** * 回溯法解决问题,只有两种选择 * * @param last 上一个选择,0 代表公司,1 代表健身房 * @param c 公司列表 * @param j 健身房列表 * @param i 当前要进行选择的位置 * @param n 总共要选择的次数 * @param cRest 当前已经休息的次数 */ public static void backtrack(int last, int[] c, int[] j, int i, int n, int cRest) { // 判断是否已经超过了 if (n == i) { if (cRest < min) { min = cRest; } return; } if (last == -1) { // 代表上一次没有选择,其他条件允许情况下可以选择公司或健身房 if (c[i] == 1) { // 选择公司 backtrack(0, c, j, i + 1, n, cRest); } if (j[i] == 1) { // 选择健身房 backtrack(1, c, j, i + 1, n, cRest); } // 选择在家休息 backtrack(-1, c, j, i + 1, n, cRest + 1); } else { // 上一次存在选择的情况 if (last == 0) { // 上一次选择了公司 if (j[i] == 1) { // 选择健身房 backtrack(1, c, j, i + 1, n, cRest); } // 在家休息 backtrack(-1, c, j, i + 1, n, cRest + 1); } else { // 上一次选择了健身房 if (c[i] == 1) { // 选择公司 backtrack(0, c, j, i + 1, n, cRest); } // 在家休息 backtrack(-1, c, j, i + 1, n, cRest + 1); } } } }
#include <iostream> #include <vector> using namespace std; int main(){ int n; cin>>n; vector<int> gongsi,jianshen; for(int i=0;i<n;i++){ int tmp; cin>>tmp; gongsi.push_back(tmp); } for(int i=0;i<n;i++){ int tmp; cin>>tmp; jianshen.push_back(tmp); } vector<vector<int>> dp(n,vector<int>(3,n)); dp[0][1]-=jianshen[0]; dp[0][2]-=gongsi[0]; for(int i=1;i<n;i++){ dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2])); dp[i][1]=min(dp[i-1][0]-jianshen[i],dp[i-1][2]-jianshen[i]); dp[i][2]=min(dp[i-1][0]-gongsi[i],dp[i-1][1]-gongsi[i]); } cout<<min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2])); }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr1 = new int[n]; int[] arr2 = new int[n]; for (int i = 0; i < n; i++) { arr1[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { arr2[i] = scanner.nextInt(); } // 休息,工作,锻炼 int[][] dp = new int[n][3]; for (int i = 0; i < n; i++) { if (i == 0) { dp[i][0] = 1; dp[i][1] = arr1[i] == 1 ? 0 : Integer.MAX_VALUE; dp[i][2] = arr2[i] == 1 ? 0 : Integer.MAX_VALUE; } else { dp[i][0] = Math.min(Math.min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]) + 1; dp[i][1] = arr1[i] == 1 ? Math.min(dp[i - 1][0], dp[i - 1][2]) : Integer.MAX_VALUE; dp[i][2] = arr2[i] == 1 ? Math.min(dp[i - 1][0], dp[i - 1][1]) : Integer.MAX_VALUE; } } // for (int i = 0; i < n; i++) { // System.out.println(Arrays.toString(dp[i])); // } System.out.println(Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2])); } }
import java.util.Scanner; //dp思路反求最大的,第一眼看以为贪心2分后来发现贪心无效,类似于买股票问题很好想 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] comp = new int[n],paly = new int[n]; for (int i = 0; i < n; i++) { comp[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { paly[i] = scanner.nextInt(); } System.out.println(retireday(comp,paly)); } private static int retireday(int[] comp, int[] paly) { int work = 0,play = 0,retire = 0; for (int i = 0; i < comp.length; i++) { int w = work,p = play,r = retire; if(comp[i]==1) work = Math.max(p,r)+1;//由于不能是连续工作那么就是pr的最大值+1 if(paly[i]==1) play = Math.max(w,r)+1;//同理上面 retire = Math.max(w,p);//选最大的一个 } int max = Math.max(Math.max(work,play),retire); return comp.length-max; } }
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> work(n), exer(n); for (int i = 0; i < n; ++i) { cin >> work[i]; } for (int i = 0; i < n; ++i) { cin >> exer[i]; } vector<vector<int>> dp(3, vector<int>(n + 1, 0)); // dp[1][i] -- work on the ith day // dp[2][i] -- exercise on the ith day // dp[0][i] -- rest on the ith day for (int i = 0; i < n; ++i) { if (work[i]) { dp[1][i + 1] = max(dp[0][i], dp[2][i]) + 1; } else { dp[1][i + 1] = max(dp[0][i], max(dp[1][i], dp[2][i])); } if (exer[i]) { dp[2][i + 1] = max(dp[0][i], dp[1][i]) + 1; } else { dp[2][i + 1] = max(dp[0][i], max(dp[1][i], dp[2][i])); } dp[0][i + 1] = max(dp[0][i], max(dp[1][i], dp[2][i])); } cout << n - max(dp[0][n], max(dp[1][n], dp[2][n])) << endl; return 0; }