SRM 595 Div1Medium

典型DP。まじめにやるときは400点はとりたいところ。

public class LittleElephantAndRGB{
	public long getNumber(String[]a,int b){
		String c="";
		for(int i=0;i<a.length;i++)c+=a[i];
		int n=c.length();
		int dp[][]=new int[n+1][b+1];
		int dp2[][]=new int[n+1][b+1];
		for(int i=0;i<n;i++){
			if(c.charAt(i)=='G')dp[i+1][1]++;
			else dp[i+1][0]++;
			for(int j=0;j<b;j++){
				if(c.charAt(i)=='G'){
					dp[i+1][j+1]+=dp[i][j];
				}else{
					dp[i+1][0]+=dp[i][j];
				}
			}
		}
		for(int i=n-1;i>=0;i--){
			if(c.charAt(i)=='G')dp2[i][1]++;
			else dp2[i][0]++;
			for(int j=0;j<b;j++){
				if(c.charAt(i)=='G'){
					dp2[i][j+1]+=dp2[i+1][j];
				}else{
					dp2[i][0]+=dp2[i+1][j];
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=1;j<b;j++){
				dp[i][j]+=dp[i][j-1];
			}
		}
		for(int i=1;i<n;i++){
			for(int j=0;j<b;j++)
				dp[i][j]+=dp[i-1][j];
		}
		long ret=0;
		for(int i=1;i<n;i++){
			ret+=(long)(i+1)*i*(n-i)/2;
		}
		//System.out.println(ret);
		for(int i=1;i<n;i++){
			for(int j=0;j<b;j++){
				ret-=dp2[i][j]*dp[i][b-j-1];
			}
		}
		return ret;
	}
}