yukicoder No.561 東京と京都

• 全部探索したいよー(と思います)
• 2の100乗の計算なんて無理よ…
• じゃあ動的計画法(dp)じゃない？
• よし書こう
• 初期の位置は東京に注意しなきゃね。

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

int n,d;
int t[101],k[101];
long long dp[101][2];
int main(){
  cin>>n>>d;
  for(int i=0;i<n;i++){
    cin>>t[i]>>k[i];
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<2;j++){
      if(i==0 && j==1)continue;//初期に京都はありえないもんね。
      if(j==0){
        dp[i+1][j]=max(dp[i][j]+t[i],dp[i+1][j]);
        dp[i+1][1]=max(dp[i][j]+k[i]-d,dp[i+1][1]);
      }else{
        dp[i+1][j]=max(dp[i][j]+k[i],dp[i+1][j]);
        dp[i+1][0]=max(dp[i][j]+t[i]-d,dp[i+1][0]);
      }
    }
  }
  cout<<max(dp[n][1],dp[n][0])<<"\n";
  return 0;
}