151 条题解
-
0
wcwswswws LV 3 @ 2006-11-03 16:37:02
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms树形DP
-
-1
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int n,m; int l[302],r[302],last[302]; int val[302]; int max(int a,int b) { return a>b?a:b; } void build(int x,int y) { if(l[y]==-1) l[y]=x; else r[last[y]]=x; last[y]=x; } int f[302][302];// f[i][j] : 以 i 为根的子树中 选j门课 最多学分 int ans=0; int work(int pos,int k) { if(pos<0||k<=0) return 0; if(f[pos][k]!=-1) return f[pos][k]; f[pos][k]=work(r[pos],k); for(int i=0;i<=k-1;i++) { f[pos][k]=max(f[pos][k],work(l[pos],i)+work(r[pos],k-i-1)+val[pos]); } return f[pos][k]; } int main() { int i,j; memset(l,-1,sizeof(l)); memset(f,-1,sizeof(f)); memset(r,-1,sizeof(r)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { int x; scanf("%d%d",&x,&val[i]); build(i,x);//i 的 父亲是 x } printf("%d",work(0,m+1)); return 0; } -
-1
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,m;
int l[302],r[302],last[302];
int val[302];
int max(int a,int b)
{
return a>b?a:b;
}
void build(int x,int y)
{
if(l[y]==-1) l[y]=x;
else r[last[y]]=x;
last[y]=x;
}
int f[302][302];// f[i][j] : 以 i 为根的子树中 选j门课 最多学分
int ans=0;
int work(int pos,int k)
{
if(pos<0||k<=0) return 0;
if(f[pos][k]!=-1) return f[pos][k];
f[pos][k]=work(r[pos],k);
for(int i=0;i<=k-1;i++)
{
f[pos][k]=max(f[pos][k],work(l[pos],i)+work(r[pos],k-i-1)+val[pos]);
}
return f[pos][k];
}
int main()
{
int i,j;
memset(l,-1,sizeof(l));
memset(f,-1,sizeof(f));
memset(r,-1,sizeof(r));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
int x;
scanf("%d%d",&x,&val[i]);
build(i,x);//i 的 父亲是 x
}
printf("%d",work(0,m+1));
return 0;
} -
-1
larryzhong LV 9 @ 2017-05-13 11:59:59
简单
-
-1
Sky1231 (sky1231) LV 10 @ 2017-01-26 16:16:44
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n,m,cn[301],c[301][301],f[301][301];
struct node1
{
int s,f;
}a[301];void dfs1(int x)
{
for (int i=1;i<=n;i++)
f[x][i]=a[x].s;
for (int i=1;i<=cn[x];i++)
{
dfs1(c[x][i]);
for (int j=m;j>0;j--)
for (int k=0;k<j;k++)
f[x][j]=max(f[x][j],f[c[x][i]][k]+f[x][j-k]);
}
}int main()
{
scanf("%d%d",&n,&m);
memset(cn,0,sizeof(cn));
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].f,&a[i].s);
c[a[i].f][++cn[a[i].f]]=i;
}
memset(f,0,sizeof(f));
m++;
dfs1(0);
printf("%d\n",f[0][m]);
} -
-1
3072276921 LV 8 @ 2016-08-26 17:32:39
这道题用网络流可以做吗
用最大权闭合子图来做可以吗 -
-1
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cstring> #define maxn 5005 using namespace std; int n,x,w[maxn]; int dp[maxn][2]; vector<int> node[maxn]; void dfs(int u){ dp[u][1]=w[u]; dp[u][0]=0; int m=node[u].size(); for (int i=0;i<m;i++){ int son=node[u][i]; dfs(son); dp[u][1]+=dp[son][0]; dp[u][0]+=max(dp[son][1],dp[son][0]); } } int main(){ cin>>n; memset(dp,0,sizeof(dp)); for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int i=1;i<=n;i++) node[i].clear(); for (int i=1;i<n;i++){ scanf("%d\n",&x); node[x].push_back(i+1); } dfs(1); printf("%d\n",max(dp[1][1],dp[1][0])); return 0; } -
-1
其实在多叉基础上DP也是可以过的……
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> node[320];
int dp[320][320];
int c[320];
int n,m;
void dfs(int u){
for (int i=0;i<node[u].size();i++){
int v=node[u][i];
dfs(v);
for (int j=m;j>=1;j--)
for (int k=1;k<=j;k++)
dp[u][j]=max(dp[u][j],dp[v][j-k]+dp[u][k]);
}
for (int i=1;i<=m;i++) dp[u][i]+=c[u];
}
int main()
{
scanf("%d%d",&n,&m);
int x;
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++){
scanf("%d%d",&x,&c[i]);
node[x].push_back(i);
}
m++;
dfs(0);
printf("%d\n",dp[0][m]);
return 0;
} -
-1
feng_lingsong LV 9 @ 2015-12-12 13:54:59
和p1418很相似
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)using namespace std;
const int maxn = 1 << 9, maxm = 1 << 9;
struct Node {
int nextNode;
Node *next;
} *N[maxn], pool[maxn << 1];int n, m, w[maxn];
int pool_cnt;
inline void addedge(int x, int y) {
Node *p = &pool[++pool_cnt];
*p = (Node){y, N[x]};
N[x] = p;
}
int vis[maxn], son[maxn][maxn], son_cnt[maxn];
int f[maxn][maxm], g[maxn][maxm];void dfs(int i) {
vis[i] = true;
for (Node *p = N[i]; p; p = p->next) {
if (!vis[p->nextNode]) {
son[i][++son_cnt[i]] = p->nextNode;
dfs(p->nextNode);
}
}
memset(f, 0, sizeof (f));
rep(j, 1, son_cnt[i]) rep(k, 0, m) rep(_k, 0, k) f[j][k] = max(f[j][k], f[j - 1][_k] + g[son[i][j]][k - _k]);
rep(j, 1, m) g[i][j] = w[i] + f[son_cnt[i]][j - 1];
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &n, &m);
++m;
int y;
rep(i, 1, n) {
scanf("%d %d", &y, &w[i]);
addedge(i, y); addedge(y, i);
}
dfs(0);
printf("%d\n", g[0][m]);
return 0;
} -
-1
Onlynagesha LV 9 @ 2015-10-17 18:25:10
-
-1
记录信息
评测状态 Accepted
题目 P1180 选课
递交时间 2015-10-09 21:05:58
代码语言 C++
评测机 VijosEx
消耗时间 30 ms
消耗内存 912 KiB
评测时间 2015-10-09 21:05:59
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 908 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 908 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 912 KiB, score = 20
测试数据 #3: Accepted, time = 15 ms, mem = 908 KiB, score = 20
测试数据 #4: Accepted, time = 15 ms, mem = 904 KiB, score = 20
Accepted, time = 30 ms, mem = 912 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int Inf=237483647;
int fir[310];
int nxt[310];
int link[310];
int val[310];
int dp[310][310];
int cnt,n,kn;
void Link(int a,int b){nxt[++cnt]=fir[a];fir[a]=cnt;link[cnt]=b;}
int search(int now)
{
dp[now][1]=val[now];
int cnt=1;
for(int i=fir[now];i;i=nxt[i])
{
cnt+=search(link[i]);
for(int j=kn+1;j>=2;j--){
for(int k=1;k<j;k++)
dp[now][j]=max(dp[now][j],dp[link[i]][k]+dp[now][j-k]);
}
}
return cnt;
}int main()
{
scanf("%d%d",&n,&kn);
for(int i=1;i<=n;i++)
for(int j=1;j<=kn;j++)
dp[n][kn]=-Inf;
for(int i=1;i<=n;i++)
{
int a;
scanf("%d%d",&a,&val[i]);
Link(a,i);
}search(0);
printf("%d",dp[0][kn+1]);
} -
-1
然而并不用输出方案……
左儿子右兄弟……长见识了
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 310
using namespace std;
int da[maxn],f[maxn][maxn];
struct treetype{
int son,bro,fa;
}tr[maxn];
void addson(int u,int v){
tr[v].bro=tr[u].son;
tr[u].son=v;
}
int dp(int u,int k){
if(!u||!k)return 0;
if(f[u][k]!=-1)return f[u][k];
for(int i=1;i<=k;i++){
f[u][k]=max(f[u][k],dp(tr[u].son,i-1)+dp(tr[u].bro,k-i)+da[u]);
}
return f[u][k]=max(f[u][k],dp(tr[u].bro,k));
}
int main(){
freopen("p1180.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int a;
scanf("%d%d",&a,&da[i]);
if(!a)a=n+1;
addson(a,i);
}
memset(f,-1,sizeof(f));
printf("%d\n",dp(n+1,m+1));
return 0;
} -
-1
测试数据 #0: Accepted, time = 0 ms, mem = 716 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 716 KiB, score = 20
测试数据 #2: Accepted, time = 15 ms, mem = 720 KiB, score = 20
测试数据 #3: Accepted, time = 31 ms, mem = 720 KiB, score = 20
测试数据 #4: Accepted, time = 62 ms, mem = 720 KiB, score = 20
Accepted, time = 108 ms, mem = 720 KiB, score = 100
代码
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
int f[302][302],score[302],brother[302],child[302];
bool visited[302][302];
int n,k;
void dfs(int i,int j)
{
if (visited[i][j]) return ;
visited[i][j]=true;
if ((i==0)||(j==0)) return;
dfs(brother[i],j);
f[i][j]=f[brother[i]][j];
for (int k=0;k<j;k++)
{
dfs(brother[i],k);
dfs(child[i],j-k-1);
f[i][j]=max(f[i][j],f[brother[i]][k]+f[child[i]][j-k-1]+score[i]);
}
}
int main()
{
cin>>n>>k;
fill(score,score+302,-10000);
score[n+1]=0;
fill(brother,brother+n+1,0);
fill(child,child+n+1,0);
for (int i=0;i<=n+1;i++)
for (int j=0;j<=n+1;j++)
{
f[i][j]=0;
visited[i][j]=false;
}
int a,b;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if (a==0) a=n+1;
brother[i]=child[a];
child[a]=i;
score[i]=b;
}
for (int i=1;i<=n+1;i++)
f[i][0]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (child[i]==0) f[i][j]=score[i];
dfs(n+1,k+1);
cout<<f[n+1][k+1];
}
wcwswswws
LV 3
@ 2006-11-03 16:37:02
