Блог пользователя red_coder

Автор red_coder, 11 лет назад, По-английски

Guys can anyone give me some hint on how to do this DP Problem..

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone pls give some hint

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Dijkstra. DP on the DAG (Direct Acyclic Graph)
    Do you understand problem?
    1) the benefit is not money.
    2) it is bad to cook the dishes two times in a row, but you can repeat some two dishes (1 3 1 3 1 3 1 ... ) and there will be profit v each time you cook this dishes.
    d[numberOfday][previousUsedDish][howManyTimesPreviosDishWasUsedInARow (range 0..3 is enough)][ourBudget] — total benefit

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      i tried but my code is not running fine.. here is my code

      /*
      written by- Piyush Golani
      language- c++
      country- India
      College- N.I.T Jamshedpur
      */
      #include <cmath>
      #include <ctime>
      #include <iostream>
      #include <string>
      #include <vector>
      #include<cstdio>
      #include<sstream>
      #include<algorithm>
      #include<cstdlib>
      #include<cstring>
      #include<map>
      #include<cctype>
      using namespace std;
      #define pb push_back
      #define all(s) s.begin(),s.end()
      #define f(i,a,b) for(int i=a;i<b;i++)
      #define F(i,a,b) for(int i=a;i>=b;i--)
      #define PI 3.1415926535897932384626433832795
      #define INF 1000000005
      #define BIG_INF 7000000000000000000LL
      #define mp make_pair
      #define eps 1e-9
      #define LL long long
      #define si(n) scanf("%d",&n)
      #define sll(n) scanf("%lld",&n)
      #define mod 1000000007
      #define mm 55
      
      
      int K,n,m;
      int C[mm],V[mm];
      double dp[22][105][mm][4];
      map<int,double> M;
      
      double solve()// dp[a][b][c][d]= maximum benifit after 'a' days with 'b' budget when previous dish used is 'c' and it is used 'd' times in a row
      {
          f(i,1,K+1)
          {
              f(j,1,m+1)
              {
                  f(k,1,n+1)
                  {
                      f(l,1,4)
                      {
                          if(l>1)
                          {
                              dp[i][j][k][l]=dp[i-1][j-C[k]][k][l-1]+V[k]*M[l];
                          }
                          else
                          {
                              f(p,1,n+1)
                              {
                                  if(p==k) continue;
                                  f(h,1,4)
                                  {
                                      dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j-C[k]][p][h]+V[k]);
                                  }
      
                              }
                          }
                      }
      
                  }
              }
          }
          double res=0.0;
          f(i,1,n+1)
          {
              f(j,1,4)
              {
                  res=max(res,dp[K][m][i][j]);
              }
          }
          return res;
      }
      
      
      int main()
      {
          M[1]=1.0;
          M[2]=0.5;
          M[3]=0.0;
          while(1){
          si(K); si(n); si(m);
          if(K==0 && n==0 && m==0) return 0;
          memset(dp,0.0,sizeof(dp));
          f(i,0,n)
          {
              si(C[i]);
              si(V[i]);
          }
          printf("%f\n",solve());
          }
          return 0;
      }