scu -- ustc

2078

### f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1)

#include <iostream>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;
typedef pair<double, double> PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-6;

int n, m;
PDD q[M];
int path[N][N];
int f[M];

int cmp(double x, double y) {
if(fabs(x - y) < eps) return 0;
else if(x < y) return -1;
else return 1;
}

int main() {
int T;
cin >> T;
while(T-- ) {
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
memset(path, 0, sizeof path);
for(int i = 0; i < n; i++) {
path[i][i] = 1 << i;
for(int j = 0; j < n; j++) {
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if(!cmp(x1, x2)) continue;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if(cmp(a, 0) >= 0) continue;
int state = 0;
for(int k = 0; k < n; k++) {
double x = q[k].x, y = q[k].y;
if(!(cmp(a*x*x + b*x, y))) state += 1 << k;
}
path[i][j] = state;
}
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 0; i + 1 < 1 << n; i++) {
int x = 0;
for(int j = 0; j < n; j++) {
if(!(i >> j & 1)) {
x = j;
break;
}
}
for(int j = 0; j < n; j++)
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
}
cout << f[(1 << n) - 1] << endl;
}
return 0;
}


### 匿名函数实现排序,to_string(int x)把x转为string

class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b){
string x = to_string(a), y = to_string(b);
return x + y > y + x;
});
string res;
for(int num : nums) res += to_string(num);
int k = 0;
while(k + 1 < res.size() && res[k] == '0') k++;
return res.substr(k);
}
};


### f[i][j][k]表示已经摆到了第i行，第i行状态是j，第i-1行状态是k的所有摆放位置的方案中的炮数最大值

#include <iostream>
#include <vector>

using namespace std;

const int N = 12, M = 1 << 10;
int f[2][M][M];
int g[110];
vector<int> state;
int cnt[M];
int n, m;

bool check(int x) {
for(int i = 0; i < m; i++)
if((x >> i & 1) && (x >> i + 1 & 1 || x >> i + 2 & 1))
return false;
return true;
}

int count(int x) {
int ans = 0;
for(int i = 0; i < m; i++)
if(x >> i & 1) ans++;
return ans;
}

int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++) {
char c;
cin >> c;
if(c == 'H') g[i] += 1 << j;
}

for(int i = 0; i < 1 << m; i++)
if(check(i)) {
state.push_back(i);
cnt[i] = count(i);
}

for(int i = 1; i <= n + 2; i++)
for(int j = 0; j < state.size(); j++)
for(int k = 0; k < state.size(); k++)
for(int u = 0; u < state.size(); u++) {
int a = state[j], b = state[k], c = state[u];
if(((a & b) | (a & c) | (b & c))) continue;
if(g[i-1] & a | g[i] & b) continue;
f[i & 1][j][k] = max(f[i & 1][j][k], f[i-1 & 1][u][j] + cnt[b]);
}

cout << f[n + 2 & 1][0][0];
return 0;
}


### f[i][s]表示填到了第i行，且第i行为s的方案数

#include <iostream>
#include <vector>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;
int w[N];
vector<int> state;
int f[N][M];
int n, m;

bool check(int x) {
for(int i = 0; i + 1 < m; i++)
if((x >> i & 1) && (x >> i + 1 & 1)) return false;
return true;
}

int main() {

cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++) {
int t;
cin >> t;
w[i] += !t * (1 << j);
}

for(int i = 0; i < 1 << m; i++)
if(check(i)) state.push_back(i);

for(int i = 0; i < state.size(); i++)
for(int j = 0; j < state.size(); j++) {
int a = state[i], b = state[j];
}

f[0][0] = 1;

for(int i = 1; i <= n + 1; i ++)
for(int j = 0; j < state.size(); j++)
if(!(state[j] & w[i])) {
f[i][j] = (f[i][j] + f[i-1][k]) % mod;
}
}

cout << f[n+1][0];

return 0;
}


### 状态压缩dp,f[i][j][s]表示前面放了i行了，且一共放了j个，第i行的状态是s

#include <iostream>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, m;
vector<int> state;
int cnt[M];
LL f[N][K][M];

bool check(int x) {
for(int i = 0; i < n; i++)
if((x >> i & 1) && (x >> (i + 1) & 1)) return false;
return true;
}

int count(int x) {
int ans = 0;
for(int i = 0; i < n; i++)
if((x >> i & 1)) ans++;
return ans;
}

int main() {
cin >> n >> m;

for(int i = 0; i < 1 << n; i++) {
if(check(i)) {
state.push_back(i);
cnt[i] = count(i);
}
}
for(int i = 0; i < state.size(); i++)
for(int j = 0; j < state.size(); j++) {
int a = state[i], b = state[j];
if((a & b) == 0 && check(a | b))
}

f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i++)
for(int j = 0; j <= m; j++)
for(int a = 0; a < state.size(); a++)
int c = cnt[state[a]];
if(j >= c) f[i][j][a] += f[i-1][j-c][b];
}
cout << f[n+1][m][0];

return 0;
}


### f[i][j]的含义是前i个字符，当前以及匹配到了T的第j个字符的方案数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, mod = 1e9 + 7;
char s[N];
int f[N][N];
int ne[N];

int main() {
int n;
cin >> n >> s + 1;
int m = strlen(s + 1);
for(int i = 2, j = 0; i <= m; i++) {
while(j && s[i] != s[j + 1]) j = ne[j];
if(s[i] == s[j + 1]) j++;
ne[i] = j;
}
f[0][0] = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
for(char k = 'a'; k <= 'z'; k++) {
int u = j;
while(u && k != s[u + 1]) u = ne[u];
if(k == s[u + 1]) u++;
if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
}
int res = 0;
for(int i = 0 ; i < m; i++) res = (res + f[n][i]) % mod;
cout << res;
return 0;
}


### 状态机f[i][0]表示在第i天，手中有股票，f[i][1]表示在第i天，没有股票第一天，f[i][2]表示在第i天，没有股票大于等于2天

#include <iostream>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][3];

int main() {
int n;
cin >> n;
f[0][0] = -INF, f[0][1] = -INF, f[0][2] = 0;
for(int i = 1; i <= n; i++) {
int w;
cin >> w;
f[i][0] = max(f[i-1][0], f[i-1][2] - w);
f[i][1] = f[i-1][0] + w;
f[i][2] = max(f[i-1][2], f[i-1][1]);
}
cout << max(f[n][1], f[n][2]);
return 0;
}


### f[i][j][0]表示从1-i天内，进行了j次交易，目前没有股票的最大值，f[i][j][1]表示从1-i天内，正在进行第j次交易，目前持有股票的最大值

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 101;

int f[N][M][2];

int main() {
int n, m;
cin >> n >> m;
memset(f, -0x3f, sizeof f);
for(int i = 0; i <= n; i++) f[i][0][0] = 0;
for(int i = 1; i <= n; i++) {
int w;
cin >> w;
for(int j = 1; j <= m; j++) {
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + w);
f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0] - w);
}
}
int ans = 0;
for(int i = 1; i <= m; i++) ans = max(ans, f[n][i][0]);
cout << ans;
return 0;
}


### 状态机,f[i][0] 表示从前i家选，且不选最后一个，f[i][1]表示从前i家选，且选最后一个

#include <iostream>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][2];

int main() {
int T;
cin >> T;
while(T-- ) {
int n;
cin >> n;
f[0][0] = 0, f[0][1] = -INF;
for(int i = 1; i <= n; i++) {
int w;
cin >> w;
f[i][0] = max(f[i-1][0], f[i-1][1]);
f[i][1] = f[i-1][0] + w;
}
cout << max(f[n][1], f[n][0]) << endl;
}
return 0;
}


### f[i]表示从前i家里面选的最大值

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int f[N];

int main() {
int T;
cin >> T;
while(T-- ) {
int n;
cin >> n;
f[0] = 0;
for(int i = 1; i <= n; i++) {
int w;
cin >> w;
if(i == 1) f[1] = w;
else f[i] = max(f[i-1], f[i-2] + w);
}
cout << f[n] << endl;
}
return 0;
}


### 贪心+01背包dp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int f[N];

struct stone {
int s, e, l;
bool operator< (const stone &W) const {
return s * W.l < l * W.s;
}
}stones[N];

int main() {
int T;
cin >> T;
for(int C = 1; C <= T; C++) {
int m = 0;
memset(f, -0x3f, sizeof f);
f[0] = 0;
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int s, e, l;
cin >> s >> e >> l;
stones[i] = {s, e, l};
m += s;
}
sort(stones, stones + n);
for(int i = 0; i < n; i++) {
int s = stones[i].s, e = stones[i].e, l = stones[i].l;
for(int j = m; j >= s; j--) {
f[j] = max(f[j], f[j-s] + max(e - l * (j - s), 0));
}
}
int ans = 0;
for(int i = 0; i < m; i++) ans = max(ans, f[i]);
printf("Case #%d: %d\n", C, ans);
}
return 0;
}