SRM 626 div2 - 思考録++

250

class SumOfPower {
public:

	int findSum( vector <int> array ) {
		vi v(array);

		int sum = 0;
		for(int i=1;i<=v.size();i++){
			for(int k=0;k<v.size();k++){
				if(k+i > v.size())continue;
				for(int j=k;j<k+i;j++){
					sum += v[j];
				}
			}
		}

		DUMP(sum);
		return sum;
	}
};

500

class FixedDiceGameDiv2 {
public:
	double getExpectation( int a, int b ) {
		int sums = 0;
		for(int i=1;i<=a;i++){
			for(int j=1;j<=b;j++){
				if(i>j)sums++;
				else break;
			}
		}

		double ret = 0;
		for(int i=1;i<=a;i++){
			int cnt = 0;
			for(int j=1;j<=b;j++){
				if(i>j)cnt++;
				else break;
			}
			ret += (double)i * ((double)cnt/(double)sums);
		}
		return ret;
	}
};

1000

long long dp[1002][50];
int d[51][51];
class NegativeGraphDiv2 {
public:
  long long findMin( int N, vector <int> s, vector <int> t, vector <int> weight, int charges ) {

    for(int i=0;i<1000;i++){
      for(int j=0;j<50;j++){
	dp[i][j] = INF;
      }
    }
    for(int i=0;i<50;i++){
      d[i][i] = 0;
      for(int j=0;j<50;j++){
	if(i!=j)d[i][j] = INF;
      }
    }
    for(int i=0;i<s.size();i++){
      s[i]--;t[i]--;
      if(s[i]!=t[i])d[s[i]][t[i]] = weight[i];
    }
    for(int k=0;k<50;k++){
      for(int i=0;i<50;i++){
	for(int j=0;j<50;j++){
	  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	}
      }
    }
    for(int i=0;i<N;i++)dp[0][i] = d[0][i];
    for(int k=1;k<=charges;k++){
      for(int i=0;i<s.size();i++){
	dp[k][t[i]] = min(dp[k][t[i]], dp[k-1][s[i]] - weight[i]);
      }
    }
    long long ans = INF;
    for(int i=0;i<=charges;i++)ans = min(ans, dp[i][N-1]);
    return ans;
  }
};