dp

/**********************************************
//DP on DAG BOJ ACM CRAFT 1005 
**********************************************/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T,N,K,W;
int in_dg[1010];

void topo_sort(int order[], vector<int> edge[]){
	order++;
	while(true){
	queue<int> q;
	for(int i=1;i<=N;i++){
		if(in_dg[i]==0) q.push(i);
	}
	if(q.empty()) return;
	while(!q.empty()){
		int x=q.front();
		*order++ = x;
		in_dg[x]=-1;
		q.pop();
		for(int i: edge[x]){
			in_dg[i]--;
		}
	}
	}
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        //입력받기
        cin>>N>>K;
        int A[N+10] = {0};
        vector<int> edge[N+10];
        vector<int> v[N+10];
        int order[1010];
        int dp[N+10] = {0};
        
        for(int i = 1; i <= N; i++) {cin>>A[i]; in_dg[i] = 0;}
        for(int i = 0,a,b; i < K; i++) {
            cin>>a>>b;
            in_dg[b]++;
            edge[a].push_back(b);
            v[b].push_back(a);
        }
        cin>>W;
        //위상 정렬
         topo_sort(order,edge);
        //dp on DAG
        for(int i = 1; i <= N; i++){
          //  cout<<order[i]<<'\n';
            int p = order[i];
            int mx = 0;
            for(auto j : v[p]) mx = max(mx, dp[j]);
            dp[p] = mx + A[p];
          //  cout<<p<<" "<<dp[p]<<'\n';
            if(p == W) {cout<<dp[p]<<'\n';break;}
        }
    }
    return 0;
}

/******************************************************************************
BOJ 11066 팰린드롬?
*******************************************************************************/
#include <iostream>
#include <cstring>
using namespace std;
int T, N;
int A[510];
int dp[510][510];
int inf = 5000001;
int main()
{
    cin>>T;
    while(T--){
        cin>>N;
        int s,e,m,cost = 0;
        for(int i = 1; i <= N; i++) cin>>A[i];
        
        memset(dp,inf,sizeof(dp));
        for(int i = 1; i <= N; i++) dp[i][i] = 0;
        
        for(int l = 2; l <= N; l++){
            for(s = 1; s <= N - l + 1; s++){
                e = s + l - 1;
                cost = 0;
                for(int i = s; i <= e; i++) cost += A[i];
                for(m = s; m < e; m++) dp[s][e] = min(dp[s][e], dp[s][m] + dp[m+1][e] + cost);
            }
        }
        cout<<dp[1][N]<<'\n';
    }
    return 0;
}

/******************************************************************************
BOJ 10942 
dp[s][e]  = dp[s+1][e-1] && (A[s] == A[e])
*******************************************************************************/

#include <iostream>

using namespace std;
int N,M;
int A[2001];
bool dp[2001][2001];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i = 0; i < N; i++) {
        cin>>A[i];
        dp[i][i] = 1;
    }

    for(int e = 1; e < N; e++){
        for(int s = e - 1; s >= 0; s--){
            if(e - s == 1) dp[s][e] = (A[s] == A[e]);
            else dp[s][e] = dp[s+1][e-1] && (A[s] == A[e]);
        }
    }
    cin>>M;
    while(M--){
        int a,b; cin>>a>>b;
        cout<<dp[a-1][b-1]<<'\n';
    }
    return 0;
}
/******************************************************************************
BOJ 13250 주사위 게임
각 사건이 벌어졌을 때의 이득과
그 사건이 벌어질 확률을 곱한 것을
전체 사건에 대해 합한 값
*******************************************************************************/

#include <iostream>

using namespace std;
int N;
double dp[1000001];
int main()
{
    cout.precision(16);
    cin>>N;
    for(int i = 1; i <= N; i++){
        for(int k = 1; k <= 6; k++){
            dp[i] += (dp[i-k] + 1) / 6.0;
        }
    }
    cout<<dp[N];
    return 0;
}
/******************************************************************************
행렬곱셈순서
dp[s][e] = min(dp[s][e],dp[s][m] + dp[m+1][e] + v[s].a*v[m].b*v[e].b)

*******************************************************************************/

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct data{int a,b;};
int N;
int dp[510][510];
vector<struct data> v;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N;
    v.push_back({0,0});
    for(int i = 0; i < N; i++){
        int a,b;
        cin>>a>>b;
        v.push_back({a,b});
    }
    
    for(int l = 1; l <= N; l++) { // 구간의 길이 1 ~ N
        for(int s = N - l + 1; s >= 1; s--){
            int e = s + l - 1;
            dp[s][e] = 1000000000;
            if(l == 1) {dp[s][s] = 0; continue;}
            for(int m = s; m <= e; m++) {
                dp[s][e] = min(dp[s][e],dp[s][m] + dp[m+1][e] + v[s].a * v[m].b * v[e].b);
                //cout<<dp[s][m]<<" "<<dp[m+1][e]<<" "<<v[s].a * v[m].b * v[e].b<<'\n';
            }
        }
        }
    cout<<dp[1][N];
}
/******************************************************************************

                  greedy + dp

*******************************************************************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 50000000000
using namespace std;
using ll = long long;
int N;
ll dp[5010][5010];
ll ans;
struct data{
    ll e,c;
    bool operator < (data chs) {return c < chs.c;}
} arr[5010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> N; 
    for(int i = 1; i <= N; i++) cin>>arr[i].e;
    for(int i = 1; i <= N; i++) cin>>arr[i].c;
    sort(arr + 1, arr + N + 1);
    memset(dp, -inf, sizeof(dp));    
    for(ll i = 1; i <= N; i++){
        for(ll j = N-1; j >= 0; j--){
            dp[i][j] = max(dp[i-1][j],max(0LL,dp[i-1][j+1]+ arr[i].e - j * arr[i].c));
        }
    }
    for(int i = 1; i <= N; i++) ans = max(ans, dp[i][0]);
    cout<<ans;
    return 0;
}
/******************************************************************************

                             bit dp 
                             BOJ 4001 컨닝
*******************************************************************************/

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
char grid[11][11];
int N,M;
bool check1(int curr, int prv){ //대각선 확인
    for(int i = 0; i < M; i++){
        if(curr & (1 << i)){ // 앉아있고
            if(i > 0 && prv & (1 << (i-1))) return false;// 왼쪽 대각선에 앉아 있거나 
            if(i < M-1 && prv & (1 <<(i+1))) return false; // 오른쪽 대각선에 앉아 있으면
        }
    }
    return true;
}
bool check2(int row, int state){ // 앉을 수 없는 자리 x인지
    for(int i = 0; i < M; i++){
        if(state & (1 << i) && grid[row][i] == 'x') return false;
    }
    return true;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
    int ans = 0; 
    cin>>N>>M;
    int dp[N+1][(1 << M)] = {0};
    memset(dp,0,sizeof(dp));
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) cin>>grid[i][j];
    vector<pair<int,int>> cand; // 상태, 학생 수
   
   for(int i = 0; i < (1 << M); i++){
       bool flag = 1;
       int cnt = i & 1;
       for(int j = 1; j < M; j++){
           if((i & (1 << j)) && (i & (1 << (j-1)))) flag = 0; // 인접하게 앉아있으면 제외
           if(i & (1 << j)) cnt++;
       }
       if(flag) cand.push_back({i,cnt});
   } 
   for(auto i : cand) if(check2(0,i.first)) dp[0][i.first] = i.second;
   for(int i = 1; i < N; i++){
   for(auto [x,y] : cand){
       if(!check2(i,x)) continue;
       for(auto[m,n] : cand){
            if(check1(x,m)) dp[i][x] = max(dp[i][x],dp[i-1][m] + y);
       }
   }
   }
   for(auto i : cand) ans = max(ans, dp[N-1][i.first]);
   cout<<ans<<'\n';
}
    return 0;
}
/******************************************************************************

                    BOJ 22984 반짝반짝2 
                    전구 개수의기댓값
*******************************************************************************/

#include <iostream>
using namespace std;
int N;
double dp[100010][2];
double p[100010];
int main()
{
    cout.precision(16);
    cin>>N;
    for(int i = 1; i <= N; i++) cin>>p[i];
    dp[1][0] = 0; dp[1][1] = 1;
    for(int i = 2; i <= N; i++){
        dp[i][0] = p[i-1] * (dp[i-1][1] + 1) + (1 - p[i-1]) * dp[i-1][0];
        dp[i][1] = p[i-1] * (dp[i-1][1]) + (1 - p[i-1]) * (1 + dp[i-1][0]) + 1;
        cout<<dp[i][0] << dp[i][1]<<'\n';
    }
    cout<<p[N] * dp[N][1] + (1 - p[N]) * dp[N][0];
    return 0;
}