DP 트레이닝(블로그 제목 쓰기 싫어)
6929 단어 zzz
제목: 나무 한 그루를 주어 각 노드에서 가장 먼 곳의 거리를 구한다.
code:
#include
#define ll long long
using namespace std;
const int maxn = 1e4 + 50;
struct node {
int nex, dis;
};
vector dge[maxn];
int d[maxn], f[maxn], son[maxn], maxxx[maxn];//d x ，son ；
//maxxx ，f x ；
bool vis[maxn];
//void dp(int x, int diss) {
// vis[x] = true;
// int maxx = 0;
// int len = dge[x].size();
// for(int i = 0; i < len; i++) {
// int y = dge[x][i].nex;
// if(vis[y]) continue;
// int dis = dge[x][i].dis;
// dp(y, diss + dis);
// if (d[y] + dis > maxx) {
// maxx = d[y] + dis;
// pre[y] = x;
// }
// }
// d[x] = maxx;
// int anss = diss;
// for (int i = 0; i < len; i++) {
// int y = dge[x][i].nex;
// if(vis[y])
// continue;
// if(pre[y] != x)
// anss = max(anss, d[y]);
// }
// maxxx[x] = anss;
// vis[x] = false;
// return;
// }
void dp(int x) {
vis[x] = true;int len = dge[x].size();
for(int i = 0; i < len; i++) {
int y = dge[x][i].nex; int dis = dge[x][i].dis;
if(vis[y]) continue;
dp(y);
if(d[y] + dis > d[x]) {
maxxx[x] = d[x];
d[x] = d[y] + dis;
son[x] = y;
}
else if(d[y] + dis > maxxx[x]) {
maxxx[x] = d[y] + dis;
}
}
}
void dfs(int x) {
vis[x] = true; int len = dge[x].size();
for (int i = 0; i < len; i++) {
int y = dge[x][i].nex; int dis = dge[x][i].dis;
if(vis[y]) continue;
if(son[x] == y)
f[y] = max(maxxx[x],f[x])+dis;
else
f[y] = max(d[x],f[x])+dis;
dfs(y);
}
}
int main() {
// freopen("in.txt", "r", stdin);
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) {
dge[i].clear(); d[i] = 0; vis[i] = false;
}
int pos; node path;
for(int i = 2; i <= n; i++) {
scanf("%d%d", &pos, &path.dis);
path.nex = i; dge[pos].push_back(path);
path.nex = pos; dge[i].push_back(path);
}
int st = 1; dp(st);
for(int i = 1; i <= n; i++) vis[i] = false; f[st] = 0;
dfs(st);
for (int i = 1; i <= n; i++) {
// printf("%d
", d[i]);
// printf("%d
", maxxx[i]);
// printf("%d %d
", i,max(f[i], d[i]));
printf("%d
", max(f[i], d[i]));
}
}
return 0;
}
남창 초청 경기
D Match Stick Game
#include
using namespace std;
#define ll long long
#define ull unsigned long long
const ll INF = -1e14;
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
ll st[2][10][100];
void init()
{
for(int i = 0;i<10;i++) for(int j = 0;j<100;j++)
{
st[0][i][j] = -INF;
st[1][i][j] = INF;
}
for(int j = 1; j <= 9; j++)
{
st[1][1][num[j]] = max(st[1][1][num[j]], j * 1ll);
st[0][1][num[j]] = min(st[0][1][num[j]], j * 1ll);
}
for(int i = 2; i < 10; i++)
{
for(int j = 0; j <= 9; j++)
{
for(int k = 100; k >= num[j]; k--)
{
st[1][i][k] = max(st[1][i][k], st[1][i - 1][k - num[j]] * 10 + j);
st[0][i][k] = min(st[0][i][k], st[0][i - 1][k - num[j]] * 10 + j);
}
}
}
st[0][1][6] = 0;
}
ll dp[105][1005];
char s[100];
int lens[105], lenn;
int main()
{
// freopen("in.txt", "r", stdin);
init();
int T;
scanf("%d", &T);
while(T--)
{
int n; lenn = 0; int sum = 0;
scanf("%d", &n); scanf("%s", s);
int len = strlen(s); int cnt = 0;
for(int i = 0; i < len; i++)
{
if(s[i] == '+' || s[i] == '-')
{
lens[lenn++] = cnt;
cnt = 0;
}
else cnt++;
if(s[i] == '-') sum += 1;
else if(s[i] == '+') sum += 2;
else sum += num[s[i] - '0'];
}
lens[lenn++] = cnt;
for(int i = 1;i<=n;i++) for(int j = 0;j<=sum;j++) dp[i][j] = INF;
len = lens[0];
int totl = 2, totr = min(sum, 7*len);
for(int j = totl; j <= totr; j++) dp[1][j] = max(dp[1][j], st[1][len][j]);
n = lenn;
for(int i = 2; i <= n; i++)
{
len = lens[i - 1];
for(int j = totr; j >= totl; j--)
{
for(int k = 2 * len; k <= 7 * len; k++)
{
dp[i][j + 2 + k] = max(dp[i - 1][j] + st[1][len][k], dp[i][j + 2 + k]);
dp[i][j + 1 + k] = max(dp[i - 1][j] - st[0][len][k], dp[i][j + 1 + k]);
}
}
totr = min(sum, totr + 7 * len + 2);
totl = totl + 2 * len + 1;
}
printf("%lld
", dp[n][sum]);
}
return 0;
}
I Max answer
#include
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 50;
struct Node
{
ll val;
int l, r;
} v[maxn];
ll s[maxn];
stack st;
int main()
{
// freopen("in.txt", "r", stdin);
int n; ll x; cin >> n; s[0] = 0;
for(int i = 1; i <= n; i++)
{
cin >> x; s[i] = s[i - 1] + x;
v[i].l = v[i].r = i; v[i].val = x;
}
v[0].val = -0x3f3f3f3f;
v[n + 1].val = -0x3f3f3f3f; v[n + 1].l = v[n + 1].r = n + 1;
int i = 1;
while(i <= n + 1)
{
if(st.empty() || v[i].val > v[st.top()].val)
st.push(i++);
else
{
v[i].l = v[st.top()].l;
st.pop();
}
}
while(!st.empty()) st.pop();
i = n + 1;
while(i >= 1)
{
if(st.empty() || v[i].val > v[st.top()].val)
st.push(i--);
else
{
v[i].r = v[st.top()].r;
st.pop();
}
}
ll ans = -0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
// cout << v[i].l << " " << v[i].r << endl;
ll tem = v[i].val * (s[v[i].r] - s[v[i].l - 1]);
ans = max(ans, tem);
}
ll sum = 0;
ll minn = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
if(sum + v[i].val < 0)
{
sum += v[i].val;
minn = min(minn, v[i].val);
ans = max(ans, minn * sum);
}
else sum = minn = 0;
}
cout << ans << endl;
return 0;
}
좋은 웹페이지 즐겨찾기
