kurocardo

4326

/*
Problem Name:股票买卖Ⅳ
algorithm tag:状态机dp
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;

const int N = 1e5 + 5;

int dp[105][2];
int w[N];
int n, k;

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

for (int i = 1; i <= n;i++)
cin >> w[i];
memset(dp, 0xcf, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n;i++){
for (int j = k; j >= 1;j--){
dp[j][0] = dp[j][0];
dp[j][0] = max(dp[j][0], dp[j][1] + w[i]);
dp[j][1] = dp[j][1];
dp[j][1] = max(dp[j][1], dp[j - 1][0] - w[i]);
}
}
int res = 0;
for (int i = 0; i <= k;i++){
res = max(res, dp[i][0]);
}

cout << res << endl;
}



/*
Problem Name:大盗阿福
algorithm tag:状态机，线性dp
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
typedef pair<int,int> pii;

const int N = 1e5 + 5;
int a[N];
int dp[N][2];

int main()
{
int t;
cin >> t;

while(t--){
int n;
cin >> n;

for (int i = 1; i <= n;i++)
cin >> a[i];

for (int i = 1; i <= n;i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + a[i];
}

cout << max(dp[n][0], dp[n][1]) << endl;
}
}


/*
Problem Name:金明的预算方案
algorithm tag:有依赖的背包,分组背包，01背包，泛化背包
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

const int M = 32005;
int n, m;
int dp[65][M];
vector<int> v[65], w[65];

int main()
{
cin >> m >> n;
int idx = 0;
int cnt = 0;
for (int i = 1; i <= n;i++){
int x, y, z;
cin >> x >> y >> z;

if(z==0){
v[i].push_back(x);
w[i].push_back(y*x);
}
else{
if(v[z].size()==1){
v[z].push_back(x+v[z][0]);
w[z].push_back(y*x+w[z][0]);
}
else if(v[z].size()==2){
v[z].push_back(x + v[z][0]);
w[z].push_back(y*x + w[z][0]);
v[z].push_back(x + v[z][1]);
w[z].push_back(y*x + w[z][1]);
}
}
}
for (int i = 1; i <= n;i++){
for (int j = 0; j <= m;j++){
dp[i][j] = dp[i - 1][j];
for (int k = 0; k < v[i].size();k++){
if(j>=v[i][k])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
}
}
}

cout << dp[n][m] << endl;
}


/*
Problem Name:能量石
algorithm tag:背包,贪心
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;
int t;
int f[10005];

struct Stone
{
int s, e, l;
bool operator<(const Stone &x) const
{
return s * x.l < x.s * l;
}
} stone[105];

int main()
{
cin >> t;
int idx = 0;

while (t--) {
int n;
cin >> n;
int m = 0;
memset(f, 0xcf, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i++) {
int s, e, l;
cin >> s >> e >> l;
stone[i] = {s, e, l};
m += s;
}

//贪心缩小枚举范围
sort(stone + 1, stone + 1 + n);
//为什么使用"恰好j"而不是"不超过j"
//我的理解是这样的：首先"恰好j"加上遍历体积也是可以算出"不超过j"的最大值的
//事实上"不超过j"的是包含f[0~m]的最值，
//而我们取max的f[j-s]+"e-(j-s)*l"<-这里的j是确定的。
//所以得出来的结果会是有错的。
for (int i = 1; i <= n; i++) {
int s = stone[i].s;
int e = stone[i].e;
int l = stone[i].l;
for (int j = m; j >= s; j--) {
f[j] = max(f[j], max(f[j - s] + e - (j - s) * l, 0));
}
}

int res = 0;
for (int i = 1; i <= m; i++)
res = max(res, f[i]);

printf("Case #%d: %d\n", ++idx, res);
}
}


//背包问题求具体方案
//tag:背包九讲

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

const int N = 1005;

int n, m;
int dp[N][N];
int g[N][N];
int w[N], v[N];

void solve1()
{
cin >> n >> m;

for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}

for (int i = n; i >= 1; i--) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i + 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
}
}

int j = m;

for (int i = 1; i <= n; i++)
if (j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]) {
cout << i << " ";
j -= v[i];
}
}

void solve2()//非字典序求具体方案g数组求法
{
cin >> n >> m;

for (int i = 1; i <= n;i++){
cin >> v[i] >> w[i];
}

for (int i = 1; i <= n;i++){
for (int j = 0; j <= m;j++){
int maxv = dp[i - 1][j];
if(j>=v[i])
maxv = max(maxv, dp[i - 1][j - v[i]] + w[i]);
if(maxv==dp[i-1][j])
g[i][j] = 0;
else if(maxv==dp[i-1][j-v[i]]+w[i])
g[i][j] = 1;
}
}

cout << dp[n][m] << endl;

int j = m;

for (int i = n; i >= 1;i--){
if (j >= v[i] && g[i][j] == 1){
cout << i << " ";
j -= v[i];
}
}
}

int main()
{
solve1();
}



//贪心
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

int t;
int n, x;
int a[505];
int b[505];

int main()
{
cin >> t;

while (t--) {
cin >> n >> x;

for (int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];

sort(a + 1, a + n + 1);
bool flag = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != b[i]) {
flag = 1;
break;
}
}
int tmp = x;
int pos = 0;
for (int i = n; i >= 2; i--) {
if (b[i] < b[i - 1]) {
pos = i - 1;
break;
}
}
if (!flag) {
cout << 0 << endl;
continue;
}
int cnt = 0;
//cout << pos << " ";
for (int i = 1; i <= n; i++) {
if (x < b[i] && i <= pos) {
swap(x, b[i]);
cnt++;
}
if (i > pos && b[i + 1] < b[i] && i < n) {
swap(x, b[i]);
cnt++;
}
a[i] = b[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
if (a[i] != b[i]) {
flag = 0;
break;
}
}

if (flag)
cout << cnt << endl;
else
cout << -1 << endl;
}
}



//背包问题求方案数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9+7;
typedef pair<int,int> pii;

const int N = 1005;

int n, m;
int w[N], v[N];
int dp[N];
ll dp2[N];

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

memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
dp2[0] = 1;

for (int i = 1; i <= n;i++)
cin >> v[i] >> w[i];
//先采用恰好为m的方法求出方案数
for (int i = 1; i <= n;i++){
for (int j = m; j >= v[i];j--){
int maxv = max(dp[j], dp[j - v[i]] + w[i]);
int s = 0;
if(maxv==dp[j])
s += dp2[j] % mod;
if(maxv==dp[j-v[i]]+w[i])
s += dp2[j - v[i]] % mod;
dp[j] = maxv, dp2[j] = s % mod;
}
}
int res = 0;
//求出最大
for (int i = 0; i <= m;i++)
res = max(res, dp[i]);
ll ans = 0;
//求出方案数
for (int i = 0; i <= m;i++)
if(res==dp[i])
ans = (ans + dp2[i]) % mod;

cout << ans << endl;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

int main()
{
int t;
cin >> t;

while(t--){
int x, y;
cin >> x >> y;
cout << x - 1 << " " << y << endl;
}
}


#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

const int N = 1e6;
int t;

int main()
{
cin >> t;

while (t--) {
int n;

cin >> n;
int ans = 0;
for (int i = 1; i <= n;i++){
int sum = i * (i + 1) / 2;
if(sum>=n){
sum = sum - n;
if(sum==0||sum>=2){
ans = i;
break;
}
else{
ans = i + 1;
break;
}
}
else
continue;
}

cout<<ans<<endl;
}
}


//有依赖的背包
//泛化背包

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int,int> pii;

const int N = 104;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int dp[N][N];

{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

void dfs(int u)
{
for (int i = h[u]; ~i;i=ne[i]){

int son = e[i];

dfs(son);

for (int j = m - v[u]; j >= 0;j--)
for (int k = 0; k <= j;k++)
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
}
for (int i = m; i >= v[u];i--)
dp[u][i] = dp[u][i - v[u]] + w[u];
for (int i = 0; i < v[u];i++)
dp[u][i] = 0;
}

int main()
{
cin >> n >> m;
int root = 0;
memset(h, -1, sizeof h);
for (int i = 1; i <= n;i++){
int p;
cin >> v[i] >> w[i] >> p;
if(p==-1)
root = i;
else