NOIP2006提高组

2006提高
A.能量项链&＃xff08;区间dp&＃xff09;题解
B.金明的预算方案&＃xff08;背包dp&＃xff09;题解
C.作业调度方案&＃xff08;模拟&＃xff09;
D.2^k进制数&＃xff08;dp&＃43;高精度&＃xff09;
D写了很久&＃xff0c;代码贼丑&＃xff0c;可能是因为一天都没看到Elijahqi大佬的缘故(
然后上了节历史课回来就调过了呢x&＃xff0c;还发现Elijahqi在和他的同桌愉快的上课呢x怪不得一天都不学习oi(逃
D可以组合数学直接算&＃xff0c;也可以dp一波&＃xff0c;dp[i][j]表示一共i个数&＃xff0c;最小的为j的方案数。则dp[i][j]&＃61;∑k&＃61;j&＃43;1maxdp[i−1][k]&＃xff0c;可以后缀和优化&＃xff0c;变成dp[i][j]&＃61;dp[i][j&＃43;1]&＃43;dp[i-1][j&＃43;1],然后可以滚动数组。

A

#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 220
inline int read(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*f;
}
int n,a[N],dp[N][N];
int main(){
// freopen("a.in","r",stdin);n&＃61;read();for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) a[i]&＃61;read(),a[n&＃43;i]&＃61;a[i];for(int l&＃61;2;l<&＃61;n;&＃43;&＃43;l)for(int i&＃61;1;i&＃43;l-1<&＃61;n<<1;&＃43;&＃43;i){int j&＃61;i&＃43;l-1;for(int k&＃61;i;k1][j]&＃43;a[i]*a[j&＃43;1]*a[k&＃43;1]);}int ans&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) ans&＃61;max(ans,dp[i][n&＃43;i-1]);printf("%d\n",ans);return 0;
}

B

#include
#include
int n,m,a,b,c,v[60][3],p[60][3],f[32000],k&＃61;0;
int main(){
// freopen("testdata.in","r",stdin);scanf("%d%d",&n,&m);n/&＃61;10;for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d%d",&a,&b,&c);if(c&＃61;&＃61;0) c&＃61;i;for(int j&＃61;0;j<&＃61;2;j&＃43;&＃43;){if(v[c][j]&＃61;&＃61;0){v[c][j]&＃61;a/10;p[c][j]&＃61;v[c][j]*b;break;}}}memset(f,0,sizeof(f));for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){if(v[i][0]!&＃61;0){int v0,v1,v2,p0,p1,p2;v0&＃61;v[i][0];p0&＃61;p[i][0];v1&＃61;v[i][1];p1&＃61;p[i][1];v2&＃61;v[i][2];p2&＃61;p[i][2];for(int j&＃61;n;j>&＃61;v0;--j){if(f[j-v0]&＃43;p0>f[j]) f[j]&＃61;f[j-v0]&＃43;p0;if(j>&＃61;v0&＃43;v1&&f[j-v0-v1]&＃43;p0&＃43;p1>f[j]) f[j]&＃61;f[j-v0-v1]&＃43;p0&＃43;p1;if(j>&＃61;v0&＃43;v2&&f[j-v0-v2]&＃43;p0&＃43;p2>f[j]) f[j]&＃61;f[j-v0-v2]&＃43;p0&＃43;p2;if(j>&＃61;v0&＃43;v1&＃43;v2&&f[j-v0-v1-v2]&＃43;p0&＃43;p1&＃43;p2>f[j]) f[j]&＃61;f[j-v0-v1-v2]&＃43;p0&＃43;p1&＃43;p2;}}}printf("%d",f[n]*10);return 0;
}

C

#include
#include
#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 25
inline int read(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*f;
}
int n,m,cnt[N],id[N][N],len[N][N],ed[N],op[N*N];
bool used[N][N*N];
int main(){
// freopen("a.in","r",stdin);n&＃61;read();m&＃61;read();for(int i&＃61;1;i<&＃61;n*m;&＃43;&＃43;i) op[i]&＃61;read();for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i)for(int j&＃61;1;j<&＃61;n;&＃43;&＃43;j) id[i][j]&＃61;read();for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i)for(int j&＃61;1;j<&＃61;n;&＃43;&＃43;j) len[i][j]&＃61;read();for(int owo&＃61;1;owo<&＃61;n*m;&＃43;&＃43;owo){int x&＃61;op[owo];cnt[x]&＃43;&＃43;;int res&＃61;0;while(resif(used[id[x][cnt[x]]][&＃43;&＃43;ed[x]]) res&＃61;0;else res&＃43;&＃43;;}for(int i&＃61;ed[x]-res&＃43;1;i<&＃61;ed[x];&＃43;&＃43;i) used[id[x][cnt[x]]][i]&＃61;1;}int ans&＃61;0;for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i) ans&＃61;max(ans,ed[i]);printf("%d\n",ans);return 0;
}

D

#include
#include
#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 30010
inline int read(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*f;
}
int k,w,n,bin[10],p&＃61;0;
struct bigint{int a[210],n;bigint(){memset(a,0,sizeof(a));n&＃61;0;}void ini(){memset(a,0,sizeof(a));n&＃61;0;}friend bigint operator&＃43;(bigint x,bigint y){bigint res;res.n&＃61;max(x.n,y.n);for(int i&＃61;1;i<&＃61;res.n;&＃43;&＃43;i) res.a[i]&＃61;x.a[i]&＃43;y.a[i];for(int i&＃61;1;i<&＃61;res.n;&＃43;&＃43;i) res.a[i&＃43;1]&＃43;&＃61;res.a[i]/10,res.a[i]%&＃61;10;if(res.a[res.n&＃43;1]) res.n&＃43;&＃43;;return res;}
}dp[2][513],ans;
int main(){
// freopen("a.in","r",stdin);k&＃61;read();w&＃61;read();n&＃61;w/k;bin[0]&＃61;1;for(int i&＃61;1;i<&＃61;k;&＃43;&＃43;i) bin[i]&＃61;bin[i-1]<<1;for(int j&＃61;bin[k]-1;j>&＃61;1;--j) dp[p][j].a[1]&＃61;1,dp[p][j].n&＃61;1;for(int i&＃61;2;i<&＃61;n;&＃43;&＃43;i){int j&＃61;bin[k]-1-i&＃43;1;if(j<1) continue;dp[p^1][j&＃43;1].ini();for(;j>&＃61;1;--j){dp[p^1][j]&＃61;dp[p^1][j&＃43;1]&＃43;dp[p][j&＃43;1];ans&＃61;ans&＃43;dp[p^1][j];}p^&＃61;1;}if(n*k!&＃61;w){int j&＃61;min(bin[k]-1-n-1&＃43;1,bin[w-n*k]-1);dp[p^1][j&＃43;1].ini();for(int i&＃61;j&＃43;1&＃43;1;i<&＃61;bin[k]-1-n&＃43;1;&＃43;&＃43;i) dp[p^1][j&＃43;1]&＃61;dp[p^1][j&＃43;1]&＃43;dp[p][i];for(;j>&＃61;1;--j)dp[p^1][j]&＃61;dp[p^1][j&＃43;1]&＃43;dp[p][j&＃43;1],ans&＃61;ans&＃43;dp[p^1][j];}for(int i&＃61;ans.n;i>&＃61;1;--i) putchar(ans.a[i]&＃43;&＃39;0&＃39;);return 0;
}