A
枚举x , 然后对于确定的x , 最后总的apple数对应了唯一的orange数,因此问题转化为求apple的取值范围;
apple的取值范围: max为每个bag取最多的apple , min为每个bag取最小的apple , 容易证明[min,max]是连续的.
using namespace std;
class WinterAndPresents {
public:
long long getNumber(vector <int>, vector <int>);
};
struct node {
int a,o;
};vector<node> f;
bool cmp(node x,node y) {
if (x.a==y.a) return x.o<y.o;
return x.a<y.a;
}
long long WinterAndPresents::getNumber(vector <int> apple, vector <int> orange) {
long long ans = ;
int x = -,n = apple.size();
for (int i= ; i<n ; i++ ) {
if (x==- || x>apple[i]+orange[i]) x=apple[i]+orange[i];
f.push_back((node){apple[i],orange[i]});
}
for (int i= ; i<=x ; i++ ) {
long long big = , sml = ;
for (int j= ; j<n ; j++ ) {
if (f[j].a>=i) big += i;
else big += f[j].a;
if (f[j].o>=i) sml += ;
else sml += i-f[j].o;
}
ans += big-sml+;
}
return ans;
}B
关键在于优化dp状态.
朴素的dp是: dp[i][mask1][mask2] 在考虑第i个数时 集合1的状态为mask1 , 集合2的状态为mask2.
为了优化掉一维,应该考虑把状态设计成 dp[i][mask1^mask2] , 然后为了识别大小再用1维记录最高非0位属于哪个集合,
再换个角度来看,可以枚举最后最高非0位在位置p , 然后用dp[i][mask1^mask2][0/1]表示:
选择了i个 ; 集合1,2的异或值异或为mask1^mask2 ; mask1在p位置是0/1
就把原来的 O(maxn*mask1*mask2) 复杂度优化为O(maxn*mask1*2*log(maxn))
最后,在实现的时候可以把 (mask1^mask2) 右移p位 , 因为最高非零位之后的都无关紧要, 此时的状态数变更小了,用dfs实现可以更快.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define mod 1000000007
class WinterAndSnowmen {
public:
int getNumber(int, int);
};
int dp[][<<][],p,n,m;
int dfs(int t,int sum,int b) {
//printf("t:%d sum:%d b:%d\n",t,sum,b);
if (t==) {
// printf("p:%d sum:%d b:%d\n",p,sum,b);
if ( sum== && b== ) return ;
else return ;
}
if (dp[t][sum][b]!=-) return dp[t][sum][b];
else {
long long res = ;
if (t<=n) {
res += dfs( t- , sum^(t>>p) , b^((t>>p)&) );
}
if (t<=m) {
res += dfs(t- , sum^(t>>p) , b );
}
res += dfs( t- , sum , b );
res %= mod;
return dp[t][sum][b]=(int)res;
}
}
int WinterAndSnowmen::getNumber(int N, int M) {
int res = ;
n = N , m = M;
for (int i= ; i< ; i++ ) {
memset(dp,-,sizeof(dp));
p = i;
res += dfs(max(N,M),,);
res %= mod;
// printf("i:%d add:%d\n",i,tmp);
}
return res;
} //Powered by [KawigiEdit] 2.0!
C
又是个需要状态优化的dp.
朴素的状态设计是: f(t , r0 , g0 , b0 , r1 , g1 , b1) , 表示第t天 , 第一个shop的销售情况和第二个shop的销售情况;
但是考虑到两个shop同时营业时 , 销售情况必须一致 , 当碰到有同时营业的情况时 , 可以直接跳到下一个结束点:
于是新的状态表示为 f(t,r0,g0,b0) ;
然后再通过各种判断,来知道如何转移;
进一步优化是去掉b0的记录, 因为每天必须售出一个ball , 知道当前天t,开始天first,已经其它销售情况就能计算出b0.
最后的状态表示为f(t,r0,g0).
using namespace std;
#define maxn 510
#define mod 1000000007
class WinterAndShopping {
public:
int getNumber(vector <int>, vector <int>, vector <int>, vector <int>);
}; struct node{
int f,r,g,b;
int end() {
return f+r+g+b;
}
};vector<node> s[maxn];
int dp[maxn][][],c[maxn][maxn]; void pretreat(vector<int> f, vector<int> r, vector<int> g, vector<int> b) {
for (int i= ; i<(int)f.size() ; i++ ) {
for (int j=f[i] ; j<f[i]+r[i]+g[i]+b[i] ; j++ ) {
s[j].push_back((node){f[i],r[i],g[i],b[i]});
}
}
for (int i= ; i<maxn ; i++ ) if (s[i].size()==) {
if (s[i][].f>s[i][].f) swap(s[i][],s[i][]);
}
for (int i= ; i<maxn ; i++ ) {
c[i][] = ;
for (int j= ; j<=i ; j++ )
c[i][j] = (c[i-][j-] + c[i-][j]) % mod;
}
} long long getfct(int r,int g,int b) {
long long res = (long long)c[r+g+b][r] * (long long )c[g+b][g] % mod;
// printf("r:%d g:%d b:%d res:%lld\n",r,g,b,res);
return res;
} long long dfs(int t,int r,int g) {
if (t==) {
if (r== && g==) return ;
else return ;
}
if (dp[t][r][g]!=-) return (long long)dp[t][r][g];
else {
long long res = ;
if (s[t].size()==) res = dfs(t+,,);
else if (s[t].size()==) {
if (t+ == s[t][].end()) res = dfs(t+,,);
else {
if (r+<=s[t][].r) res += dfs(t+,r+,g);
if (g+<=s[t][].g) res += dfs(t+,r,g+);
if (t-s[t][].f-r-g+<=s[t][].b) res += dfs(t+,r,g);
}
res %= mod;
}
else if (s[t].size()==) {
node s0 = s[t][] , s1 = s[t][];
int b = (t-s0.f-(r+g));
if (s0.end() == s1.end()) {
if (s0.r-r==s1.r && s0.g-g==s1.g && s0.b-b==s1.b) {
res = getfct(s1.r,s1.g,s1.b) * dfs(s1.end(),,) % mod;
}
} else if (s0.end() < s1.end()) {
if (s0.r-r<=s1.r && s0.g-g<=s1.g && s0.b-b<=s1.b) {
res = getfct(s0.r-r,s0.g-g,s0.b-b) * dfs(s0.end(),s0.r-r,s0.g-g) % mod;
}
} else if (s0.end() > s1.end()) {
if (s1.r<=s0.r-r && s1.g<=s0.g-g && s1.b<=s0.b-b) {
res = getfct(s1.r,s1.g,s1.b) * dfs(s1.end(),r+s1.r,g+s1.g) % mod;
}
}
}
dp[t][r][g] = (int)res;
return res;
}
} int WinterAndShopping::getNumber(vector <int> f, vector <int> r, vector <int> g, vector <int> b) {
pretreat(f,r,g,b);
memset(dp,-,sizeof(dp));
long long ans = dfs(,,);
return (int)ans;
}