社区讨论

关于 dp 顺序的疑问

P1450[HAOI2008] 硬币购物参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo7uu1pt
此快照首次捕获于
2023/10/27 08:07
2 年前
此快照最后确认于
2023/10/27 08:07
2 年前
查看原帖
为什么必须先枚举要转移的物品,然后再转移?
具体看代码(前面 150 行代码头不用管)
CPP
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <random>
#include <numeric>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define ctz __builtin_ctz
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO
{
	template<class T>
	void write(T x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>=10)
		{
			write(x/10);
		}
		putchar(x%10^48);
	}
	template<class T>
	void read(T& x)
	{
		x=0;
		T f=1;
		char ch=getchar();
		while(!isdigit(ch))
		{
			if(ch=='-')f=-1;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
		x*=f;
	}
}
namespace Math
{
	template<class T>
	T quick_pow(T a,T b,T p=-1)
	{
		if(p==-1)
		{
			T res=1;
			while(b)
			{
				if(b&1)res=res*a;
				a*=a;
				b>>=1;
			}
			return res;
		}
		else
		{
			T res=1;
			while(b)
			{
				if(b&1)res=res*a%p;
				a=a*a%p;
				b>>=1;
			}
			return res;
		}
	}
	template<class T>
	T inv(T x,T p)
	{
		return quick_pow(x,p-2,p);
	}
	struct Matrix
	{
		std::vector<std::vector<ll>> mp;
		ll p;
		int size;
		void init(int siz,ll mod=-1,bool isdw=0)
		{// 第二个参数:是否设为单位矩阵 
			p=mod;	
			size=siz;
			mp.resize(siz);
			for(int i=0;i<siz;i++)
			{
				mp[i].resize(siz);
				for(int j=0;j<siz;j++)
				{
					mp[i][j]=0;
				}
				if(isdw)mp[i][i]=1;
			}
		}
		Matrix operator *(const Matrix& b)
		{
			assert(p==b.p);//模数不一样寄掉 
			Matrix res;
			res.init(std::max(size,b.size),p);
			for(int i=0;i<size;i++)
			{
				for(int k=0;k<size;k++)
				{
					for(int j=0;j<size;j++)
					{
						if(k>=b.size||j>=b.size)continue;
						res.mp[i][j]+=mp[i][k]*b.mp[k][j];
						if(res.p!=-1)res.mp[i][j]%=res.p;
					}
				}
			}
			return res;
		}
	};
	Matrix quick_pow_mat(Matrix a,ll b)
	{
		Matrix res;
		res.init(a.size,a.p,1);
		while(b)
		{
			if(b&1)res=res*a;
			a=a*a;
			b>>=1;
		}
		return res;
	}
}
typedef __int128 int128;
const int maxn=1e5+5;
int128 c1,c2,c3,c4,n;
int128 d1,d2,d3,d4,s;
int128 f[maxn];
int128 calc(int128 x)
{
	if(s-x>=0)return f[s-x];
	return 0;
}
int main()
{
	FastIO::read(c1);
	FastIO::read(c2);
	FastIO::read(c3);
	FastIO::read(c4);
	FastIO::read(n);
	f[0]=1;/*
	挂掉的转移
	FOR(i,1,100000)
	{
		if(i>=c1)f[i]+=f[i-c1];
		if(i>=c2)f[i]+=f[i-c2];
		if(i>=c3)f[i]+=f[i-c3];
		if(i>=c4)f[i]+=f[i-c4];
	}*/
	FOR(i,c1,100000)f[i]+=f[i-c1];
	FOR(i,c2,100000)f[i]+=f[i-c2];
	FOR(i,c3,100000)f[i]+=f[i-c3];
	FOR(i,c4,100000)f[i]+=f[i-c4];
	while(n--)
	{
		FastIO::read(d1);
		FastIO::read(d2);
		FastIO::read(d3);
		FastIO::read(d4);
		FastIO::read(s);
		d1++;
		d2++;
		d3++;
		d4++;
		d1*=c1;
		d2*=c2;
		d3*=c3;
		d4*=c4;
		FastIO::write((int128)calc(0)-(int128)calc(d1)-(int128)calc(d2)-(int128)calc(d3)-(int128)calc(d4)+(int128)calc(d1+d2)
			+(int128)calc(d1+d3)+(int128)calc(d1+d4)+(int128)calc(d2+d3)+(int128)calc(d2+d4)+(int128)calc(d3+d4)
			-(int128)calc(d1+d2+d3)-(int128)calc(d1+d3+d4)-(int128)calc(d1+d2+d4)-(int128)calc(d2+d3+d4)+(int128)calc(d1+d2+d3+d4));
		putchar(10);
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...