社区讨论
关于 dp 顺序的疑问
P1450[HAOI2008] 硬币购物参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo7uu1pt
- 此快照首次捕获于
- 2023/10/27 08:07 2 年前
- 此快照最后确认于
- 2023/10/27 08:07 2 年前
为什么必须先枚举要转移的物品,然后再转移?
具体看代码(前面 150 行代码头不用管)
CPP具体看代码(前面 150 行代码头不用管)
#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 条回复,欢迎继续交流。
正在加载回复...