SRM 585 Div1

初のDiv1。

250

拍子抜けのEasy。まさにEasy。画像が読み込めなかった。

class TrafficCongestion{
public:
   int theMinCars(int treeHeight){
      long long ans=1;
      for(int i=0;i<treeHeight;i++){
         if(i%2==0)ans=ans*2-1;
         else ans=ans*2+1;
         ans%=1000000007;
      }
      return (int)ans;
   }
};

500

初Div1の500。手応え的にはDiv2の500と1000の中間くらい。セグメンテーションフォールト。 考えた方法は、dp。 順に数字の種類を増やしていく。増やす場所によってLISが変化するので、頑張ってDP。 頑張れなかった。

以下頑張れなかったコード。（実行してもセグフォ）

#include <vector>
using namespace std;
long long dp[1300][40];
const long long MOD=1000000007;
long long combi(long long a,long long b){
   if(a<b)return 0;
   long long ans=1;
   for(int i=0;i<a-b;i++){
      ans*=a-i;
      ans/=i+1;
   }
   return ans;
}
long long homopro(long long a,long long b){
   return combi(a+b-1,b);
}
class LISNumber{
public:
   int count(vector <int> cardsnum, int K){
      long long l=cardsnum[0];
      dp[cardsnum[0] ][0]=1;
      for(int i=1;i<cardsnum.size();i++){
         l+=cardsnum[i];
         for(int k=0;k<1297;k++){
            int h=cardsnum[i];
            for(int s=0;s<=h;s++){
               int r=h-s;
               dp[k+s][i]+=dp[k][i-1]*combi(k,r)*homopro(l-k+r,s)%MOD;
               dp[k+s][i]%=MOD;
            }
         }
      }
      return dp[K][cardsnum.size()-1];
   }
};