luogu四月计划

发布于 2019-03-31  132 次阅读


发现自己好久没写博客了。。。于是准备记录一下在洛谷刷水题的做题思路。
1510
裸的背包,可以看成一个体积为c,装n个物体,每个物体的价值和体积分别是物体的体积和物体的体力。最后再判断一下。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
const int maxn = 100050;
int val[maxn],f[maxn],q[maxn],v,n,c,res=0,flag=0;
int main(){
    memset(f,0,sizeof(f));
    scanf("%d%d%d",&v,&n,&c);
    rep(i,1,n) scanf("%d%d",&val[i],&q[i]);
    rep(i,1,n)
    dep(j,c,q[i]){
        f[j] = max(f[j],f[j-q[i]]+val[i]);
        if(f[j] >= v)
        res = max(res,c-j),flag = 1;
    }
    if(flag) printf("%d\n",res);
    else printf("Impossible\n");
    return 0;
}

1466
dp,状态为f[i][j],表示考虑前i个数和为j的方案数。所以转移的话只有选或选不了。
f[i][j]=f[i-1][j]+f[i-1][j-i]

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
const int maxn = 1005;
LL f[maxn][maxn],N,sum;
int main(){
	scanf("%lld",&N);
	sum=(N*(N+1))>>1;
	if(sum%2==1){printf("0\n");return 0;}
	f[1][0]=f[1][1]=1;
	rep(i,2,N)
	rep(j,0,sum){
		if(j>i)
		f[i][j]=f[i-1][j]+f[i-1][j-i];
		else f[i][j]=f[i-1][j];
	}
	printf("%lld\n",f[N][sum>>1]);
	return 0;
}
	

1352
在树上进行dp,用前向星存图,自底向上dp;

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <sstream>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
using namespace std;
const int maxn = 6e3+10;
int head[maxn],c[maxn],h[maxn],f[maxn][2],rot,cnt = 0;
struct Edge{
	int ne,to;
}ed[maxn];
inline int max(int x,int y){
	return x>y?x:y;
}
inline void add1(int x,int y){
	ed[++cnt].to = y; ed[cnt].ne = head[x]; head[x] = cnt;
}
void dfs(int x){
	f[x][1] = h[x];
	for(register int i = (head[x]); i; i = ed[i].ne){
		int start = ed[i].to;
		dfs(start);
		f[x][1] += f[start][0];
		f[x][0] += max(f[start][0],f[start][1]);
	}
}
 int main(){
	int N;scanf("%d",&N);
	rep(i,1,N) scanf("%d",&h[i]);
	rep(i,1,N-1){
		int A,B;
		scanf("%d%d",&A,&B);
		++c[A];
		add1(B,A);
	}
	rep(i,1,N){
		if(!c[i]) {rot = i;break;}
	}
	dfs(rot);
	printf("%d",max(f[rot][0],f[rot][1]));
	return 0;
}
	

我是一个局部环,你是我的唯一极大理想。