oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1117 學測念不完，可是又要北市賽了QQ只好把市賽題刷一刷，希望至少市賽不要出事 最近真的好笨，只會一些straightforward的題目，這題還是被雷的才出來的。 總之核心問題就是我們不能一次做太多事、要一步一步來，畢竟他每次要輸出的字串也沒多長。 那所以我們就每次要知道第n個矩陣的第i,j元素，而這可以直接根據定義直接看他在哪一塊，並且遞迴下去就會得知答案了。 #include <bits/stdc++.h> using namespace std; bool go(int,int,int); int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); for(int n, i, a, b;cin >> n >> i >> a >> b;){ for(int j=a;j<=b;j++) cout << (go(n, i-1, j-1)?"+1":"-1") << " \n"[j==b]; } return 0; } bool go(int n, int x, int y) { if(n == 0) return 0; int tl = (1<<(n-1)); if(x >= tl and y >= tl) return go(n-1, x-tl, y-tl)^1; if(x >= tl) x -= tl; if(y >= tl) y -= tl; return go(n-1, x, y); }

題目連結: https://tioj.infor.org/problems/1914 搞了好久，才發現我一開始的DP式是錯的QQ 這題難點應該就是DP式吧，不過我也不知道我怎麼想到的，所以這邊就給式子就好：$dp[i][j] = \min_{i \leq k < j }(dp[i][k]+dp[k+1][j])-[a_i==a_j]$(其中[]是 艾佛森括號 )，然後$dp[i][j]$的意思是把$[i, j]$填滿的最小步數，然後轉移方法就是枚舉中點，代表先把$[i, k]$填好再填$[k+1, j]$，而減一的部份則是因為明顯若首尾相同，那我們在填左邊的時候就可以順便拉一條過去到右邊，就不需要右邊又在畫一遍了。 #include <bits/stdc++.h> using namespace std; const int N = 200 + 5; int arr[N], dp[N][N]; int main(){ int t; scanf("%d", &t); while(t--){ int n, m; scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) scanf("%d", arr+i); for(int i=1;i<=n;i++) dp[i][i]=1; for(int i=n;i>=1;i--){ for(int j=i+1;j<=n;j++){ dp[i][j]=1<<25; for(int k=i;k+1<=j;k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]); if(arr[i]==arr[j]) dp[i][j]--; } } printf("%d\n", dp[1][n]); } return 0; }