[TIOJ] 1134. 1.蓋房子問題
題目連結: http://tioj.infor.org/problems/1134 想了想覺得把1換成-1, 0換成1之後會有好事情，然後似乎可以做類似最大子矩陣的方式，但是我不知道該怎麼用。 被雷了之後才發現其實我只要把兩個問題合在一起就好了，一個是最大子矩陣，一個是某種找有多少大於零的序列的問題。首先我們可以先對一維用前綴和之後枚舉頂跟底，接著就變成一維的問題了，變成一維的問題後就是要問說對於所有大於零的序列中，最長是多少，作法也是考慮枚舉前綴和，每次只要查小於當前前綴和的所有鍵值中最小的值是多少，接著就把當前前綴和當做鍵值，現在的位置當作值插到某種資料結構就好了。 #include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x), end(x)
const int N = 200 + 5;
const int INF = 1<<30;
class LiSan{
private:
vector<int> vv;
public:
inline void init(){vv.clear();}
inline void insert(int x){vv.push_back(x);}
inline void done(){
sort(ALL(vv));
vv.resize(distance(vv.begin(), unique(ALL(vv))));
}
inline int size(){return vv.size();}
inline int get(int x){
return distance(vv.begin(), lower_bound(ALL(vv), x));
}
inline int inv_get(int x){return vv[x];}
...