[关闭]
@KirinBill 2017-10-08T11:29:23.000000Z 字数 3558 阅读 587

2017.9.28 NOIP模拟赛

题解 套题

题简单也要静下心来做...

目录


矩阵

82XB6.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. #include <cstring>
  31. using std::min;
  32. const int MAXN=505;
  33. int n,m;
  34. int a[MAXN];
  35. inline long long DP(){
  36. static long long dp[MAXN][MAXN];
  37. for(int len=2;len<=m;++len){
  38. for(int l=2,r,lim=m-len+1;l<=lim;++l){
  39. r=l+len-1;
  40. dp[l][r]=dp[l+1][r]+(long long)a[l-1]*a[l]*a[r];
  41. for(int mid=l+1;mid<r;++mid)
  42. dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]+(long long)a[l-1]*a[mid]*a[r]);
  43. }
  44. }
  45. return dp[2][m];
  46. }
  47. int main(){
  48. setIO("A");
  49. read(n);
  50. read(a[++m]),read(a[++m]);
  51. for(int i=2,tmp;i<=n;++i)
  52. read(tmp),read(a[++m]);
  53. write(DP());
  54. return 0;
  55. }

时态同步

82F2T.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. using std::max;
  31. const int MAXN=5e5+5;
  32. int n,rt;
  33. int he[MAXN];
  34. long long ans;
  35. long long dson[MAXN];
  36. struct line{int to,nex,w;}ed[MAXN<<1];
  37. inline void addE(int u,int v,int w){
  38. static int cnt=0;
  39. ed[++cnt]=(line){v,he[u],w};
  40. he[u]=cnt;
  41. }
  42. void DFS(int u,int fa,long long d){
  43. for(int i=he[u],v;i;i=ed[i].nex){
  44. v=ed[i].to;
  45. if(v!=fa){
  46. DFS(v,u,d+ed[i].w);
  47. dson[u]=max(dson[u],dson[v]+ed[i].w);
  48. }
  49. }
  50. for(int i=he[u],v;i;i=ed[i].nex){
  51. v=ed[i].to;
  52. if(v!=fa) ans+=dson[u]-dson[v]-ed[i].w;
  53. }
  54. }
  55. int main(){
  56. setIO("B");
  57. read(n),read(rt);
  58. for(int i=1,u,v,w;i<n;++i){
  59. read(u),read(v),read(w);
  60. addE(u,v,w),addE(v,u,w);
  61. }
  62. DFS(rt,0,0);
  63. write(ans);
  64. return 0;
  65. }

葡萄

82P1M.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  5. using std::max;
  6. const int MAXN=10005,MAXSTA=1<<10;
  7. int n,k,a,b,sum;
  8. int cnt[MAXSTA],grape[MAXN];
  9. inline void prepare(){
  10. for(int i=1,lim=1<<k;i<lim;++i)
  11. cnt[i]=cnt[i>>1]+(i&1);
  12. }
  13. inline int DP(){
  14. static int dp[2][MAXSTA];
  15. memset(dp,-0x3f,sizeof(dp));
  16. for(int i=0,lim=1<<k,tmp,j;i<lim;++i){
  17. if(cnt[i]<a || b<cnt[i]) continue;
  18. dp[k&1][i]=0;
  19. tmp=i,j=1;
  20. while(tmp){
  21. if(tmp&1) dp[k&1][i]+=grape[j];
  22. tmp>>=1,++j;
  23. }
  24. }
  25. for(int i=k+1,lim=1<<k,mod=lim-1,top=lim>>1;i<=n;++i){
  26. for(int j=0,tmp,l;j<lim;++j){
  27. if(cnt[j]<a || b<cnt[j]) continue;
  28. dp[i&1][j]=max(dp[~i&1][j<<1&mod],dp[~i&1][j<<1&mod|1])+grape[i]*(bool)(j&top);
  29. }
  30. }
  31. int ret=INT_MIN;
  32. for(int i=0,lim=1<<k;i<lim;++i){
  33. if(a<=cnt[i] && cnt[i]<=b)
  34. ret=max(ret,dp[n&1][i]);
  35. }
  36. return ret;
  37. }
  38. int main(){
  39. freopen("C.in","r",stdin);
  40. freopen("C.out","w",stdout);
  41. scanf("%d%d%d%d",&n,&k,&a,&b);
  42. for(int i=1;i<=n;++i){
  43. scanf("%d",&grape[i]);
  44. sum+=grape[i];
  45. }
  46. prepare();
  47. printf("%d",(DP()<<1)-sum);
  48. return 0;
  49. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注