• 先骂一下MSN space太恶心了,本来一个帖子的,害我分了三段,支持长文本你要死人所!老子!!!~~~ 你居然还是MS,你不怕侮辱了MS高贵的名声哟。[小声说,MS好像在开源界本来就不是很好的名声,再加上最近的官司]我很崇拜MS的,你们要赶快改进哟!不能光用sliverlight渲染界面就完料洒,关键是性能,注意是性能,骂累了,休息下,接着学习图论,我会保持每天至少两道DP的量的。[不含图论的题目]加油!!!!!!
  • 能量守恒,先灭了三道没过的,结果。。。又来三道,还有道搜索,日子难过!!!要尽量AC
  • OJ宏调试问题,呵呵,又是一个原文没有feedback好的帖子,不过都很牛,小菜收了![注意宏扩散的问题,undef掉,切记]
#define dbg(x) cerr<<#x<<" : "<<x<<endl 
#define

DEBUG
#define LOG_FILE __FILE__".log"
#ifdef DEBUG
#define dbgprint(format,args…) fprintf(stderr, format, ##args)
#define logprint(format,args…) {FILE* fp=fopen(LOG_FILE,"a+");fprintf(fp,"line %d: "format,__LINE__,##args);fclose(fp);}
#else
#define dbgprint(format,args…)
#define logprint(format,args…)
#endif

  • 这两道题目很水,水得不行了!放最后吧!
1。大家都拿它来秒杀,结果。。。我还用了16ms。。。。
Source Code
Problem: 1163User: orlando22
Memory: 8132KTime: 16MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAX=1001;
    int r, n, a[MAX][MAX];
    long d[MAX][MAX], maxL=LONG_MIN;
    //1<=R<=1000, 0<=value<=100
    
    int main()
    {
        //implementation
        memset((void*)&d[0][0], 0, sizeof(int)*MAX*MAX);
        memset((void*)&a[0][0], 0xff, sizeof(long)*MAX*MAX);
        cin>>r;
        for(int i=0; i<r; i++)
           for(int j=0; j<=i; j++)
              cin>>a[i][j];
        //dp
        d[0][0]=a[0][0];maxL=LONG_MIN;
        for(int i=1; i<r; i++){//[i][j][k], j<=i
            for(int j=0; j<=i; j++){
                long max=LONG_MIN;
                if(max<d[i-1][j]+a[i][j]&&j<=i-1) max=d[i-1][j]+a[i][j];
                if(max<d[i-1][j-1]+a[i][j]&&j-1>=0)  max=d[i-1][j-1]+a[i][j];
                d[i][j]=max;
                if(i==r-1&&max>maxL) maxL=max;
            }
        }
        if(r==1) maxL=a[0][0];
        cout<<maxL<<endl;
    
        return 0;
    }
  • 环形石子合并[线型的用四边形加速可解,这里主要改了下方程f[i][l]]
User ID: orlando22 
Problem ID:

1137
Solution ID: 76470
Language: GNU
C++
Result: Accepted

[Text Mode …] | [ColorCode Mode …] | [Copy to clipboard]

[PS:这道题目本来很水,结果我还贡献了3-5个WA,原因在与贪心的边界有问题!LLV又天真地被欺骗了]

  1. #include <iostream>
  2.  
  3. using namespace std;
  4. const int MAX=102;//0...100..101
  5. int n,r,p[MAX],maxS[MAX][MAX],minS[MAX][MAX],sum1[MAX]={0},sum2[MAX]={0};
  6.  
  7. //declaration
  8. int callen(int i, int len);
  9. //implementation
  10. inline int callen(int i, int len){
  11. if(len==1) return p[i];
  12. int j=i+len-1;
  13. if(j<=n) return sum1[j]-sum1[i-1];
  14. else{
  15. j=j%n;//start with i, end with j-1;
  16. return sum1[j]+sum2[i];
  17. }
  18. }
  19.  
  20. int main()
  21. {
  22. //implementation
  23. while(cin>>n){
  24. memset((void*)maxS, 0, sizeof(maxS)),memset((void*)minS, 0, sizeof(minS));
  25. memset((void*)sum1, 0, sizeof(sum1)),memset((void*)sum2, 0, sizeof(sum2));
  26. memset((void*)p, 0, sizeof(p));
  27. for(int i=1; i<=n; i++) cin>>p[i];
  28. //pre-calculation for different length
  29. for(int i=1; i<=n; i++) sum1[i]=sum1[i-1]+p[i];
  30. for(int i=n; i>=1; i--) sum2[i]=sum2[i+1]+p[i];
  31. //instead of table using callen
  32. for(int l=2; l<=n; l++){
  33. for(int i=1; i<=n; i++){
  34. int score=callen(i, l), cmax=INT_MIN, cmin=INT_MAX;
  35. for(int k=1; k<=l-1; k++){
  36. int p=i+k;
  37. if(p>n) p=p%n;
  38. int tmp1=maxS[i][k]+maxS[p][l-k]+score;//merge with l-k
  39. if(tmp1>cmax) cmax=tmp1;
  40. int tmp2=minS[i][k]+minS[p][l-k]+score;
  41. if(tmp2<cmin) cmin=tmp2;
  42. }
  43. maxS[i][l]=cmax,minS[i][l]=cmin;
  44. }
  45. }
  46. int max=INT_MIN,min=INT_MAX;
  47. for(int i=1; i<=n; i++){
  48. if(max<maxS[i][n]) max=maxS[i][n];
  49. if(min>minS[i][n]) min=minS[i][n];
  50. }
  51. cout<<min<<endl<<max<<endl;
  52. }
  53. return 0;
  54. }

Advertisements