A. Timofey and a tree

這個不算是dp，就是一個思維題，好難想的思維題，看了題解才寫出來的，

把點和邊分開，如果一條邊的兩個點顏色不同就是特殊邊，特殊邊兩邊連的點就叫特殊點，

如果一個點的被計算的次數等于特殊邊的次數，則說明它是我們所求的點

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int num[maxn], a[maxn];
pair<int, int>pii[maxn];int main()
{int n;scanf("%d", &n);for(int i=1;i<n;i++){int u, v;scanf("%d%d", &u, &v);pii[i] = make_pair(u, v);}int ans = 0;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i=1;i<n;i++){int u = pii[i].first, v = pii[i].second;if(a[u]!=a[v]){num[u]++;num[v]++;ans++;}}for(int i=1;i<=n;i++){if(num[i]==ans){printf("YES\n");printf("%d\n",i);return 0;}}printf("NO\n");return 0;
}

A

?A. Chain Reaction

這個我覺得挺難的。。。。

網上題解，dp[i]來表示激活第i個位置，從前面往后推到第i個位置，這個塔存留下來的數量。

這個是線性的，后面那個位置都是由前面的那個位置推過來的，如果我們選了后面那個位置，如果后面的無法把前面的那個位置炸掉

那么只能不炸，或者由最后添加的那個點來炸掉之前你需要炸掉的區間。

這個題目簡單，是因為可以轉化成線性的，不過我覺得好難想。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define inf 0x3ff3f3f
using namespace std;
const int maxn = 1e6 + 10;
int d[maxn], dp[maxn];
int main()
{int n;scanf("%d", &n);int mm = 0;for(int i=1;i<=n;i++){int a;scanf("%d", &a);scanf("%d", &d[a]);mm = max(mm, a);}if (d[0]) dp[0] = 1;int res = min(n, n - dp[0]);for(int i=1;i<=mm;i++){if (d[i] == 0) dp[i] = dp[i - 1];else {if (d[i] >= i) dp[i] = 1;else {dp[i] = dp[i - 1 - d[i]] + 1;}}res = min(res, n - dp[i]);}printf("%d\n", res);return 0;
}

A

?

轉載于:https://www.cnblogs.com/EchoZQN/p/11026591.html

總結

以上是生活随笔為你收集整理的dp cf 20190615的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。