HDU 4001 To Miss Our Children Time DP-白红宇

HDU 4001 To Miss Our Children Time DP

阅读量：5892 次

发布时间：2019-06-19

本文共 1797 字，大约阅读时间需要 5 分钟。

排序后DP，注意要用long long 的地方。

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
                    
                      pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template
                     
                       T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template
                      
                        T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); // freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=1001;const int mod=100000007;struct block{ int a,b,c,d; bool operator < (const block &x) const { if(a!=x.a) return a
                       
                        x.d; else return c>x.c; }};block da[maxn];ll dp[maxn];ll f(int k,int n){ if(k>n)return 0; if(dp[k]>=0)return dp[k]; ll maxx=0; for(int i=k+1;i<=n;i++) { if(da[i].d==0){ if(da[i].a>=da[k].a&&da[i].b>=da[k].b) maxx=max(maxx,f(i,n)+da[i].c); }else if(da[i].d==1){ if(da[i].a>=da[k].a&&da[i].b>=da[k].b&&(ll)da[i].a*da[i].b>(ll)da[k].a*da[k].b) maxx=max(maxx,f(i,n)+da[i].c); }else if(da[i].d==2){ if(da[i].a>da[k].a&&da[i].b>da[k].b) maxx=max(maxx,f(i,n)+da[i].c); } } return dp[k]=maxx;}int main(){ //freopen("in.txt","r",stdin); int n; da[0]=(block){ 0,0,0,0}; while(cin>>n&&n) { for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&da[i].a,&da[i].b,&da[i].c,&da[i].d); if(da[i].a