2018-07-21
简单dp递推一下,一维的会挂,改二维就好了.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月21日 星期六 12时13分38秒
File Name :a.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +10;
int MOD = 1e9 + 7;
int dp[N][2];
int sum[N];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int q, k;
scanf("%d%d", &q, &k);
dp[0][0] = 1;
for(int i = 1; i < N; ++i) {
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD;
if(i - k >= 0)
dp[i][1] = dp[i-k][0];
}
for(int i = 1; i < N; ++i)
sum[i] = (sum[i-1] + (dp[i][1] + dp[i][0] ) % MOD) % MOD;
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", (sum[r] - sum[l-1] + MOD) % MOD);
}
return 0;
}
贪心迷之错误,队友DP过了,类似与股票买卖. dp[i][0] 表示第i天持有物品, 可以从 dp[i-1][1] , dp[i-1][0]转移到 dp[i][1] 表示第i天没有物品, 同样也是上述两种情况转移
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#define mst(a, b) memset(a, b, sizeof(a))
#define clr(a) mst(a, 0)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define lowbit(x) (x&(-x))
#define fi first
#define se second
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define lt u << 1
#define rt u << 1 | 1
#define pr(x) cout << #x << " = " << x << " ";
#define prl(x) cout << #x << " = " << x << endl;
using namespace std;
template<typename T>
ostream& operator << (ostream & os, const vector<T>& v) {
for(int i = 0; i < v.size(); i++) os << v[i] << " ";
}
template<typename T>
ostream& operator << (ostream & os, const set<T>& v) {
for(typename set<T>::iterator it = v.begin(); it != v.end(); it++) os << *it << " ";
}
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> V;
typedef pair<ll, int> P;
typedef long double LDB;
typedef double DB;
P dp[N][2], ans;
ll a[N];
const ll INF = 1e18;
int main() {
//freopen("a.in", "r", stdin);
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
rep(i, 1, n) {
cin >> a[i];
}
dp[0][0] = P(0, 0);
dp[0][1] = P(-INF, inf);
rep(i, 1, n) {
dp[i][0] = max(P(dp[i - 1][1].fi + a[i], dp[i - 1][1].se - 1), dp[i - 1][0]);
dp[i][1] = max(dp[i - 1][1], P(dp[i - 1][0].fi - a[i], dp[i - 1][0].se - 1));
}
P ans = max(dp[n][0], dp[n][1]);
cout << ans.fi << " " << -ans.se << "\n";
}
return 0;
}
首先明确题意,是把很多个集装箱里的产品移动到某一个集装箱里.而不是把几个集装箱移动到一个位置,坑了我好久…
然后可以发现,移动的最优情况一定是移动一个区间内的产品,而不是分开的.而且是还移动到中位数所在的集装箱内. 其次,移动的产品数量显然可以二分来求. 那么我们就可以二分答案,然后枚举左端点,区间的右端点和中位数点则一定是单调的. 然后因为我们无法确定,零散的几个产品实在左端点还是右端点.所以要左右两边都枚举一遍.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月24日 星期二 15时06分22秒
File Name :g.cpp
************************************************ */
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 1024;
int n;
ll t;
int x[N], a[N];
ll prec[N], prew[N], sufc[N], sufw[N];
ll d(int i, int j) {
return 1ll * abs(x[j] - x[i]);
}
void init() {
for(int i = 1; i <= n; ++i) prec[i] = prec[i-1] + a[i];
for(int i = n; i >= 1; --i) sufc[i] = sufc[i+1] + a[i];
for(int i = 1; i <= n; ++i) prew[i] = prew[i-1] + prec[i-1] * d(i, i-1) * 2;
for(int i = n; i >= 1; --i) sufw[i] = sufw[i+1] + sufc[i+1] * d(i, i+1) * 2;
}
ll cal_pre(int l, int r) {
return prew[r] - prew[l-1] - prec[l-1]*(x[r] - x[l-1]) * 2;
}
ll cal_suf(int l, int r) {
return sufw[l] - sufw[r+1] - sufc[r+1]*(x[r+1] - x[l]) * 2;
}
bool check(ll m) {
ll m2 = m/2 + 1;
int l = 1, r = 1, mid = 1;
while(1) {
//cout << r << endl;
while(r <= n && prec[r] - prec[l-1] < m) r++;
while(mid <= n && prec[mid] - prec[l-1] < m2) mid++;
if(r > n || mid > n) break;
ll c = m - (prec[r-1] - prec[l-1]);
ll s = cal_pre(l, mid) + cal_suf(mid, r-1) + c * (x[r] - x[mid]) * 2;
if(s <= t) return 1;
l++;
}
l = n, r = n, mid = n;
while(1) {
while(l >= 1 && prec[r] - prec[l-1] < m) l--;
while(mid >= 1 && prec[mid] - prec[l-1] < m2) mid--;
if(l < 1 || mid < 1) break;
ll c = m - (prec[r] - prec[l]);
ll s = cal_pre(l + 1, mid) + cal_suf(mid, r) + c*(x[mid] - x[l]) * 2;
if(s <= t) return 1;
r--;
}
return 0;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%lld", &n, &t);
for(int i = 1; i <= n; ++i)
scanf("%d", &x[i]);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
//cout << "/";
init();
//cout << "/";
ll l = 1, r = prec[n];
ll ans = 0;
while(l <= r) {
ll m = l + r >> 1;
if(check(m)) {
l = m + 1;
ans = m;
}
else
r = m - 1;
}
cout << ans;
return 0;
}
给你一棵树,点有点权.要你找出三条不相交的路径,使得点权最大.
树形DP f[i][j] 表示,以i为根的子树,i不包含在路径内,有j条路径的最大权值之和. g[i][j] 表示,以i为根的子树,i包含在路径内,有j条路径的最大权值之和.
方程的转移就很明了了: 对于以u为根的子树,先dfs其所有子节点v为根的子树. 然后在子树中找到每种 路径条数和根节点度数 的情况的最大权值之和. 然后在更新到f[u], g[u]之中.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月25日 星期三 23时27分53秒
File Name :h.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PB push_back
const int N = 4e5 + 1024;
int n, w[N];
ll f[N][4], g[N][5];
vector<int> G[N];
void dfs(int u, int fa = 0) {
ll a[4][3] = {0}, b[4][3] = {0}, c[4][3] = {0};
for(int v : G[u]) if(v != fa) {
dfs(v, u);
memset(b, 0, sizeof b);
for(int k = 0 ; k <= 3; ++k) {
b[k][0] = f[v][k];
b[k][1] = g[v][k];
}
memset(c, 0, sizeof c);
for(int k = 0; k <= 3; ++k)
for(int l = 0; k + l <= 3; ++l)
for(int o = 0; o <= 2; ++o)
for(int p = 0; o + p <= 2; ++p) {
c[l+k][o+p] = max(c[k+l][o+p], a[k][o] + b[l][p]);
}
memcpy(a, c, sizeof c);
}
for(int k = 0; k <= 3; ++k) f[u][k] = max( f[u][k], a[k][0]);
for(int k = 1; k <= 3; ++k) for(int l = 0; l <= 2; ++l)
f[u][k] = max(f[u][k], a[k-1][l] + w[u]);
for(int k = 0; k <= 3; ++k) for(int l = 0; l <= 1; ++l)
g[u][k] = max(g[u][k], a[k][l] + w[u]);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for(int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].PB(v);
G[v].PB(u);
}
dfs(1);
printf("%lld\n", f[1][3]);
return 0;
}
先找出没有坏块的拜访规律: $ans = n/2*4 + (n&1)$
然后再发现坏块只影响所在行所在列的两辆车,而n为奇数时. 中间行列要特殊处理. 其实是个sb题,但是当时脑子比较混乱.菜鸡
/* ***********************************************
Author :JiangYu
Created Time :2018年07月21日 星期六 14时54分53秒
File Name :i.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool visx[N], visy[N];
int number1() {
int res = 0;
for(int i = 1; i < N; ++i) if(visx[i]) res++;
return res;
}
int number2() {
int res = 0;
for(int i = 1; i < N; ++i) if(visy[i]) res++;
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,k;
cin >> n >> k;
int ans = n / 2 * 4;
if(n&1) ans++;
bool flag = 0;
while(k--) {
int x, y;
cin >> x >> y;
visx[x] = 1;
visy[y] = 1;
//if(n&1 && x == n/2+1&& y == n/2+1) flag = 1;
}
//cout << ans;
ans -= number1() + number2();
if(n&1 && visx[n/2+1] && visy[n/2+1])ans++;
else if(n&1 && !visy[n/2+1] && visx[n/2+1]) ans++;
else if(n&1 && visy[n/2+1] && !visx[n/2+1]) ans++;
cout << max(0, ans);
return 0;
}
好题,我们可以通过判断每一棵作物被撒肥料次数是否等于被撒相同肥料的次数来判断一棵作物是否死了. 前者可以通过二维前缀和$O(nm)$求出,后者则考虑到二维偏序,可以利用树桩数组进行快速求解. 先将肥料按类保存,然后通过$x,y$排序,对于每个点就都可以在$log$内求出相同的肥料有多少种了.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月24日 星期二 14时04分02秒
File Name :j.cpp
************************************************ */
#include <bits/stdc++.h>
#define PB push_back
#define all(a) a.begin(), a.end()
using namespace std;
int n, m;
const int N = 1e6 + 1024;
int id(int i, int j) {return i * (m+2) + j;}
struct node {
int X1, Y1, X2, Y2;
void read() {
scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
X1++, X2++, Y2++, Y1++;
}
};
struct nod{
int x, y, val;
};
vector<nod> v[N<<1];
int c[N<<3];
int bit[N<<1];
bool cmp(const nod &o, const nod &p) {
if(o.x == p.x && o.y == p.y) return abs(o.val) > abs(p.val);
if(o.x == p.x)
return o.y < p.y;
return o.x < p.x;
}
int lowbit(int k) {return k & -k;}
void add(int pos, int x) {
while(pos <= m) {
bit[pos] += x;
pos += lowbit(pos);
}
}
int sum(int pos) {
int res = 0;
while(pos) {
res += bit[pos];
pos -= lowbit(pos);
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t, x;
scanf("%d%d%d", &n, &m, &t);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
scanf("%d", &x);
v[x].PB(nod{i, j, 0});
}
while(t--) {
node now;
now.read();
int k;
scanf("%d", &k);
v[k].PB(nod{now.X1-1, now.Y1-1, 1});
v[k].PB(nod{now.X2, now.Y2, 1});
v[k].PB(nod{now.X1-1, now.Y2, -1});
v[k].PB(nod{now.X2, now.Y1-1, -1});
c[id(now.X1-1, now.Y1-1)]++;
c[id(now.X2, now.Y2)]++;
c[id(now.X1-1, now.Y2)]--;
c[id(now.X2, now.Y1-1)]--;
}
for(int i = 1; i <= n ; ++i) {
for(int j = 1; j <= m; ++j) {
c[id(i, j)] += c[id(i-1, j)] + c[id(i, j-1)] - c[id(i-1, j-1)];
}
}
int ans = 0;
for(int i = 0; i <= n*m; ++i) {
sort(all(v[i]), cmp);
for(int j = 0; j < v[i].size(); ++j) {
if(v[i][j].val == 0) {
if(c[id(v[i][j].x, v[i][j].y)] == sum(v[i][j].y))
ans++;
}
else {
add(v[i][j].y, v[i][j].val);
}
}
for(int j = 0; j < v[i].size(); ++j) {
if(v[i][j].val)
add(v[i][j].y, -v[i][j].val);
}
}
printf("%d\n", n*m - ans);
return 0;
}