#include<iostream>
#include<cstdio>
using namespace std;

int a[25][1005];
int dp[25][1005];

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
        int n,m;
        cin>>n>>m;
        int i,j,k;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);

        for(i=0;i<m;i++)
            dp[0][i]=-105;
        for(i=0;i<n;i++)
            dp[i][0]=-105;
        dp[0][1]=dp[1][0]=0;

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //（x+1,y），(x,y+1)
                for(k=2;k<=m;k++)
                {
                    if(j%k==0)
                        dp[i][j]=max(dp[i][j],dp[i][j/k]);   //(x,y*k)
                }
                dp[i][j]+=a[i][j];
            }

        cout<<dp[n][m]<<endl;
    }
    return 0;
}

/*
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
*/

How to Type

3
Pirates
HDUacm
HDUACM

8
8
8

Hint
The string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8.
The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8
The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8
 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char str[105];
int dp[105][2];   //dp[i][1]表示完成i打印Cap灯亮,dp[i][0]表示完成i打印Cap灯灭

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
       cin>>str+1;
       int i;
       int len=strlen(str+1);
       dp[0][0]=0,dp[0][1]=2;   //初始状态为灯灭
       for(i=1;i<=len;i++)
       {
           if(str[i]>=‘A‘&&str[i]<=‘Z‘)   //为大写
           {
               dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+2);
               dp[i][0]=min(dp[i-1][1]+2,dp[i-1][0]+2);
           }
           else     //为小写
           {
               dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+2);
               dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+2);
           }
       }

       int res=min(dp[len][0],dp[len][1]+1);
       cout<<res<<endl;
    }
    return 0;
}

/*
3
Pirates
HDUacm
HDUACM
*/