桃之夭夭 灼灼其华 之子于归 宜其室家。
我想了好久 hash的思想我真的是不太会貌似 我的时间都在不经意间留走 今天去开学籍证明和考试被踩 我想了很多的东西。
焦神当年一脸凶相 刷题上千 才能成功 我想再这样浪费时间怎么能追上当年的他呢。
我不能再让 时间白白的溜走了 我真的不习惯考试被人踩，我想成功！
这道题 搜了一下题解是 可以开动态的数组我不太会开 这个方法不是太靠谱 。
hash 一下数组的值，这是学长的做法 看其代码我也真的是不太懂。
网上搜了一个题解这个要是再不懂 不懂也得懂。
我学习了一番其中的进制思想但是仍是不懂他的操作，我不知道为什么我不懂，自己写一个吧，思想都会了 编码自己搞。
首先这道题不可写的原因是数组的范围不好固定那么我们 使用p进制数数组的大小就可以确定了100000；
这么大貌似可以设状态了，考虑p进制是哪几个进制 首先身为进制那么必须是要比某个数的值域要大（不能进位的那种）
其次是考虑p怎么取出每一位上的数字 考虑十进制 是这样的 x=g*10^0+s*10^1+b*10^2...
那么取出第k位的数字就是 x%m(k+1)/mk就能够取出这一位的数字了。
考虑每一位的进制是多少 那不就是 每个地方的值+1么
取出之后状态就有了 对于 每座山如果某一位已经超过了我的进制的位数了那么 直接不要了因为肯定累加不到其价值了。
不出一料 我写挂了 感性的写 我想 对于这个p进制数其实就跟多维数组一样了只不过就是将其压缩了一下我认为,这样的话我就可以把状态糅合在一起了
并且取值得时候非常快的就取到了对应位置上的数字 这要dp就很容易进行转移了。
的确需要一些思考但是并不是特别的难，至于这种进制思想我想需要好好理解。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define INF 2147483646 #define ll long long #define R register #define mod 64123 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(ll x) { x<0?putchar('-'),x=-x:0; ll num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=200000,maxn=150; int n,m,maxx; int p[maxn],a[maxn],v[maxn],b[maxn]; int f[MAXN],flag[maxn]; int c[maxn][maxn]; inline int max(int x,int y){return x>y?x:y;} int main() { //freopen("1.in","r",stdin); n=read();m=read(); p[0]=1; for(int i=1;i<=m;++i) { a[i]=read(); p[i]=p[i-1]*(a[i]+1); } for(int i=1;i<=m;++i)maxx=maxx+p[i-1]*a[i]; for(int i=1;i<=n;++i) { v[i]=read(); for(int j=1;j<=m;++j) { c[i][j]=read(); b[i]+=c[i][j]*p[j-1]; if(c[i][j]>a[j])flag[i]=1; } } for(int i=1;i<=n;++i) { if(flag[i])continue; for(int j=maxx;j>=b[i];j--) { int target=1; for(int k=1;k<=m;++k)if(j%p[k]/p[k-1]<c[i][k]){target=0;break;} if(target)f[j]=max(f[j],f[j-b[i]]+v[i]); } } put(f[maxx]); return 0; }
吐槽一下 校oj的题解真不好...