Mots-clés » D.P.

LightOj - 1017 - Brush (III)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1017
Method : DP


#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				106
#define ll				long long
#define ull				unsigned long long
#define MOD				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)			cout<<#x<<"--> " << x << endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T > inline void extEuclid(T  a, T b, T &x, T &y, T &gcd) {
      x = 0; y = 1; gcd = b;
      T m, n, q, r;
      for (T u=1, v=0; a != 0; gcd=a, a=r) {
            q = gcd / a; r = gcd % a;
            m = x-u*q; n = y-v*q;
            x=u; y=v; u=m; v=n;
      }
}

// The result could be negative, if it's required to be positive, then add "m"
template <class T > inline T  modInv(T n, T m) {
      T x, y, gcd;
      extEuclid(n, m, x, y, gcd);
      if (gcd == 1) return x % m;
      return 0;
}



/*************************** END OF TEMPLATE ****************************/


int iAr;
int CS;

int SZ;
struct Node {
      int val;
      int index;
      int howMany;
};
Node T;
int DP;
int C;

int cal (int index , int R )
{
      
      if(index >= SZ || R <= 0 ) {
            return 0;
      }
      if(DP[R] !=-1 ) return DP[R];
      int Rp = C;
      int p = 0;
      p = max( CS - (index ? 185 mots de plus
Lightoj

[LC] Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs… 302 mots de plus

OJ Problem

USACO: Number Triangles

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=numtri


/*
PROG: numtri
LANG: C++
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<=b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int ara;
int dp;
int r;

int func(int i,int j)
{
    if(i>r || j>r) return 0;

    int &ret=dp[i][j];
    if(ret!=-1) return ret;
    ret=0;
//    return ret=max(ara[i][j]+func(i+1,j),ara[i][j]+func(i+1,j+1));
    return ret=ara[i][j]+max(func(i+1,j),func(i+1,j+1));
}

int main()
{
    CIN;
    freopen("numtri.in","r",stdin);
    freopen("numtri.out","w",stdout);

    cin>>r;
    REP(i,1,r) REP(j,1,i) cin>>ara[i][j];
    ms(dp,-1);
    cout<<func(1,1)<<endl;
    return 0;
}


USACO

Display your picture here...

Display picture or profile picture or whatever the heck they are called these days. I hate them.
I am sure they were started off with right intentions but all it does now is encourage vanity. 236 mots de plus

Personal

First Oath Rite

I actually did the rite on Sunday, but haven’t written it up till now.  The ritual itself was adapted from the one in DP Through the Wheel of the Year.   327 mots de plus

Dp